One-Stroke Sketch (一筆書き) Recursive Solution

date

Apr 25, 2023

slug

recursive1

author

status

Public

Problem Description

Given n and m as the length and height of a square, return the combination of paths that should run through the entire square. Moving diagonally is forbidden.

For example:

Input:
n, m = 1, 2

Return:
2

Recursive Solution

Thought

The first solution that came to my mind is a brute-force approach, which involves trying out all possible combinations. Since each position allows for four directions (up, down, left, and right), the problem can be represented as a tree structure, where each node has four children. Therefore, the problem can be approached as a search through the tree. The initial solution that came to my mind is a recursive one.

Solution

def find( x , y ,arr):
    # out of bound
    if x<1 or y <1 or x >n or y > m:
        return 0
    # update the access record 
    arr[x-1,y-1]+=1
    
    if (arr == 2).any():
        return 0
    if arr.sum()== n*m:
        if (arr == target).all():
            return 1
    return find(x-1 , y,arr.copy()) + find(x+1 , y,arr.copy()) + find(x , y -1,arr.copy()) + find(x , y+1,arr.copy())

sum_ = 0
n , m = 4,4
for i in range(n):
    for j in range(m):
        
        target = np.ones((n,m))
        init = np.zeros((n,m))
        sum_ += find(i+1,j+1,init)
print(sum_)