# 2664. The Knight’s Tour¶

• Time: $O(2^{mn})$
• Space: $O(2^{mn})$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 class Solution { public: vector> tourOfKnight(int m, int n, int r, int c) { vector> ans(m, vector(n, -1)); dfs(m, n, r, c, 0, ans); return ans; } private: static constexpr int dirs[8][2] = {{1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}, {-2, -1}, {-2, 1}, {-1, 2}}; bool dfs(int m, int n, int i, int j, int step, vector>& ans) { if (step == m * n) return true; if (i < 0 || i >= m || j < 0 || j >= n) return false; if (ans[i][j] != -1) return false; ans[i][j] = step; for (const auto& [dx, dy] : dirs) if (dfs(m, n, i + dx, j + dy, step + 1, ans)) return true; ans[i][j] = -1; return false; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 class Solution { public int[][] tourOfKnight(int m, int n, int r, int c) { int[][] ans = new int[m][n]; Arrays.stream(ans).forEach(A -> Arrays.fill(A, -1)); dfs(m, n, r, c, 0, ans); return ans; } private static final int[][] dirs = {{1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}, {-2, -1}, {-2, 1}, {-1, 2}}; private boolean dfs(int m, int n, int i, int j, int step, int[][] ans) { if (step == m * n) return true; if (i < 0 || i >= m || j < 0 || j >= n) return false; if (ans[i][j] != -1) return false; ans[i][j] = step; for (int[] dir : dirs) if (dfs(m, n, i + dir[0], j + dir[1], step + 1, ans)) return true; ans[i][j] = -1; return false; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 class Solution: def tourOfKnight(self, m: int, n: int, r: int, c: int) -> List[List[int]]: dirs = ((1, 2), (2, 1), (2, -1), (1, -2), (-1, -2), (-2, -1), (-2, 1), (-1, 2)) ans = [[-1] * n for _ in range(m)] def dfs(i: int, j: int, step: int) -> bool: if step == m * n: return True if i < 0 or i >= m or j < 0 or j >= n: return False if ans[i][j] != -1: return False ans[i][j] = step for dx, dy in dirs: if dfs(i + dx, j + dy, step + 1): return True ans[i][j] = -1 return False dfs(r, c, 0) return ans