Question
There is n by n grid, you have to start at row 0, column 0 (the top left) I want to know the number of routes that explore all the compartments of the grid, and do not pass the compartment already searched. Example: n = 2 → 2 paths
def dfs(size, cur_pos, route : list):
# size : size of grid, cur_pos : (current_row, current_column). each_row/col starts at 0
# route : list consists of positions so far. ex) [(0,0),(1,0),(1,1)]
route.append(cur_pos)
# append current position at route list first
# escape condition
if len(route) == pow(size, 2): # if length of route is same as the size of the grid
result_list.append(route) # add 1 to the number of path
return
to_move = [(1,0),(-1,0),(0,1),(0,-1)] # amount to move. down/up/right/left
for i in range(4):
next_pos = (cur_pos[0] + to_move[i][0], cur_pos[1] + to_move[i][1])
# set next position
if 0 <= next_pos[0] < size and 0 <= next_pos[1] < size: # if next position is still in the grid
if next_pos not in route: # if next position is not already searched
dfs(size, next_pos, route) # search recursively
result_list = [] # save each complete routes
input_size = int(input())
dfs(input_size, (0,0), [])
print(len(result_list)) # always print 1....
This code always prints 1...
I think the route variable seems to be not cleared when each search is done, but I have no idea how to fix that. Does anyone know how to make it do that?
