难度: Medium
Submission
运行时间: 954 ms
内存: 16.0 MB
class Solution:
def tourOfKnight(self, m: int, n: int, r: int, c: int) -> List[List[int]]:
dirs = [(-2, -1), (-2, 1), (-1, 2), (1, 2), (2, 1), (2, -1), (1, -2), (-1, -2)]
board = [[-1]*n for _ in range(m)]
def dfs(r, c, depth):
board[r][c] = depth
if depth == m*n-1: return True
for dr, dc in dirs:
nr, nc = r + dr, c + dc
if nr < 0 or nr >= m or nc < 0 or nc >= n or board[nr][nc] >= 0: continue
if dfs(nr, nc, depth+1): return True
board[r][c] = -1
return False
dfs(r, c, 0)
return board
Explain
此题解采用了深度优先搜索（DFS）算法来解决骑士巡逻的问题，即在m*n的棋盘上，骑士从指定位置(r, c)开始尝试遍历整个棋盘的所有位置，每个位置只能访问一次。题解中首先定义了骑士移动的8种可能方向。在棋盘数组中，使用-1表示该位置尚未被访问。DFS函数尝试将骑士从当前位置移动到下一个合法位置，并递归地继续执行DFS，直到覆盖所有棋盘格子或无法继续移动。如果某次DFS调用在完成全局遍历后返回True，则整个搜索过程停止。若从某位置出发的所有移动后继都不可能完成任务，则会将其重新标记为-1并回溯到上一步。
时间复杂度: O(8^(m*n))
空间复杂度: O(m*n)
class Solution:
def tourOfKnight(self, m: int, n: int, r: int, c: int) -> List[List[int]]:
dirs = [(-2, -1), (-2, 1), (-1, 2), (1, 2), (2, 1), (2, -1), (1, -2), (-1, -2)] # 定义骑士可以移动的8个方向
board = [[-1]*n for _ in range(m)] # 初始化棋盘，未访问的位置标记为-1
def dfs(r, c, depth):
board[r][c] = depth # 标记当前位置为已访问
if depth == m*n-1: return True # 如果访问了所有格子，返回True
for dr, dc in dirs: # 遍历所有可能的移动方向
nr, nc = r + dr, c + dc # 计算新的位置坐标
if nr < 0 or nr >= m or nc < 0 or nc >= n or board[nr][nc] >= 0: continue # 检查新位置是否合法且未访问
if dfs(nr, nc, depth+1): return True # 递归移动到新位置
board[r][c] = -1 # 回溯，撤销当前位置的访问标记
return False # 如果无法完成遍历，返回False
dfs(r, c, 0) # 从初始位置开始DFS
return board # 返回棋盘上的访问顺序
Explore
在实现深度优先搜索（DFS）时，为了确保骑士不会走出棋盘外，我在代码中添加了对新位置坐标的合法性检查。具体来说，对于每个可能的移动方向，我计算出新的位置坐标 (nr, nc)，然后检查这些坐标是否满足 nr >= 0、nr < m、nc >= 0 和 nc < n 来保证新的位置仍在棋盘范围内。此外，还需要检查目标位置是否已经被访问过，即 board[nr][nc] 是否大于等于0。只有当新的位置合法且未被访问时，才会继续执行DFS。这样，通过边界检查，可以确保骑士的每次移动都不会超出棋盘的边界。
回溯是一种通过试错来寻找所有（或部分）解的问题解决方法。在深度优先搜索中，如果从当前位置出发的所有可能的移动都不能完成对棋盘的完整遍历，即所有的递归DFS调用都返回了False，则当前路径不能构成解决方案。在这种情况下，我们需要撤销最近的移动，并尝试其他可能的移动。具体到本题，当DFS无法通过当前路径完成棋盘遍历时，我会将当前位置的访问标记（即 board[r][c]）重置为-1（表示未访问），然后返回False给上一层递归，表示当前路径不可行。这样，算法会回到上一个位置，尝试其他的移动方向。回溯的过程是解决这类搜索问题的核心，它使得算法能够探索棋盘上的所有可能路径，直到找到一个成功遍历整个棋盘的路径或确认没有解决方案。
在选择深度优先搜索（DFS）而非广度优先搜索（BFS）来解决骑士巡逻问题的主要考虑是问题的性质和目标。DFS通过探索尽可能深的路径，有助于快速找到一个可能的解决方案，即一条能覆盖所有棋盘格子的路径。相比之下，BFS以层级方式广泛搜索，更适合于找到最短路径问题，而在本问题中，我们不仅需要找到覆盖所有格子的路径，而且路径的长度固定为棋盘格子的数量。此外，DFS在空间复杂度上通常比BFS更优，因为BFS需要存储在搜索过程中的所有状态，而DFS仅需存储一条路径上的状态。因此，考虑到问题的需求和资源效率，DFS是更合适的选择。