在N*M网格的左上角有一个机器人，机器人可以上下左右移动，但每次遍历不能访问同一个cell超过一次。如何找到机器人到达右下角的总路径数？
（机器人无需访问每个单元格即可使路径有效）
我认为有一个递归的解决方案，但我无法以某种方式得到它。
到目前为止我得到的是：
def initialize(row, cols):
grid = [ [ 0 for c in range(cols) ] for r in range(rows) ]
pos_r, pos_c = 0, 0
grid[pos_r][pos_c] = 1 # set start cell as visited
dst_x, dst_y = len(grid)-1, len(grid[0])-1 # coords of bottom-right corner
print move_robot(grid, dst_x, dst_y, pos_r, pos_c)
def move_robot(grid, dst_x, dst_y, pos_r, pos_c, prev_r=None, prev_c=None):
num_ways = 0
if reached_dst(dst_x, dst_y, pos_r, pos_c):
undo_move(grid, pos_r, pos_c)
undo_move(grid, prev_r, prev_c)
return 1
else:
moves = get_moves(grid, pos_r, pos_c)
if len(moves) == 0:
undo_move(grid, prev_r, prev_c)
return 0
for move in moves:
prev_r = pos_r
prev_c = pos_c
pos_r = move[0]
pos_c = move[1]
update_grid(grid, pos_r, pos_c)
num_ways += move_robot(grid, dst_x, dst_y, pos_r, pos_c, prev_r, prev_c)
return num_ways
if __name__ == '__main__':
initialize(4, 4)
为了简洁起见，我省略了一些函数定义。Get_moves检索所有合法的移动，检查每个移动是否仍在棋盘上，以及该单元格是否已被访问。Update_grid将指定的单元格设置为“1”，这意味着已访问。Undo_move相反，将指定的单元格设置为“0”。
对于最简单的情况（2*2网格），我得到了正确的答案，但是对于较大的网格，输出总是太低。我的代码有什么问题，有没有更简单的方法来做到这一点？
递归非常简单，但在递归时应该小心创建矩阵的副本以获得良好的结果：
from copy import copy, deepcopy
def calc(i, j, mat):
if i < 0 or j < 0 or i >= len(mat) or j >= len(mat[0]):
return 0 # out of borders
elif mat[i][j] == 1:
return 0 # this cell has already been visited
elif i == len(mat)-1 and j == len(mat[0])-1:
return 1 # reached destination (last cell)
else:
mat[i][j] = 1 # mark as visited
# create copies of the matrix for the recursion calls
m1 = deepcopy(mat)
m2 = deepcopy(mat)
m3 = deepcopy(mat)
m4 = deepcopy(mat)
# return the sum of results of the calls to the cells:
# down + up + right + left
return calc(i+1, j, m1) + calc(i-1, j, m2) + calc(i, j+1, m3) + calc(i, j-1, m4)
def do_the_robot_thing(m, n):
# an un-visited cell will be marked with "0"
mat = [[0]*n for x in xrange(m)]
return calc(0, 0, mat)
print(do_the_robot_thing(3, 3))
输出：
12
