如何在多项式时间内解决 Rat in Maze Puzzle？
How to solve in polynomial time Rat in Maze Puzzle?
我最近在一次采访中被问到 this question：
A Maze is given as N*N binary matrix of blocks where source block is
the upper left most block i.e., maze[0][0] and destination block is
lower rightmost block i.e., maze[N-1][N-1]. A rat starts from source
and has to reach destination. The rat can move only in two directions:
forward and down. (or 4 in advanced problem). In the maze matrix, 0
means the block is dead end and 1 means the block can be used in the
path from source to destination.
我的回答是link中提到的那个，就是使用回溯。来自 link:
的高级伪代码
If destination is reached
print the solution matrix
Else
a) Mark current cell in solution matrix as 1.
b) Move forward in horizontal direction and recursively check if this
move leads to a solution.
c) If the move chosen in the above step doesn't lead to a solution
then move down and check if this move leads to a solution.
d) If none of the above solutions work then unmark this cell as 0
(BACKTRACK) and return false.
面试官对我的回答很惊讶，显然期待多项式时间的解决方案。
这个问题是否存在多项式时间解法？
这可以使用 BFS 在线性时间内解决。
问题实际上是一个图形，其中所有单元格都是顶点，单元格的可能移动是边。您正在寻找从某个源到目的地的最短路径，这正是 BFS 所做的。
（请注意，在仅允许 "down" 和 "right" 的简化问题中，有效路径具有相同的长度。但对于具有 4 个允许方向的更复杂的问题，情况并非如此）
要生成实际路径，您需要通过 "remembering" 探索的每个节点的父节点来跟踪路径。这在问题中讨论：How can I find the actual path found by BFS?
我最近在一次采访中被问到 this question：
A Maze is given as N*N binary matrix of blocks where source block is the upper left most block i.e., maze[0][0] and destination block is lower rightmost block i.e., maze[N-1][N-1]. A rat starts from source and has to reach destination. The rat can move only in two directions: forward and down. (or 4 in advanced problem). In the maze matrix, 0 means the block is dead end and 1 means the block can be used in the path from source to destination.
我的回答是link中提到的那个，就是使用回溯。来自 link:
的高级伪代码If destination is reached
print the solution matrix
Else
a) Mark current cell in solution matrix as 1.
b) Move forward in horizontal direction and recursively check if this
move leads to a solution.
c) If the move chosen in the above step doesn't lead to a solution
then move down and check if this move leads to a solution.
d) If none of the above solutions work then unmark this cell as 0
(BACKTRACK) and return false.
面试官对我的回答很惊讶，显然期待多项式时间的解决方案。
这个问题是否存在多项式时间解法？
这可以使用 BFS 在线性时间内解决。
问题实际上是一个图形，其中所有单元格都是顶点，单元格的可能移动是边。您正在寻找从某个源到目的地的最短路径，这正是 BFS 所做的。
（请注意，在仅允许 "down" 和 "right" 的简化问题中，有效路径具有相同的长度。但对于具有 4 个允许方向的更复杂的问题，情况并非如此）
要生成实际路径，您需要通过 "remembering" 探索的每个节点的父节点来跟踪路径。这在问题中讨论：How can I find the actual path found by BFS?