Skip to content

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<vector<int>> tourOfKnight(int m, int n, int r, int c) {
    vector<vector<int>> ans(m, vector<int>(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<vector<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 (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