# 2664. The Knight’s Tour



````java
```java
class Solution {
    private static final int[][] DIRS = {{ 2, 1}, { 2, -1}, { -2, 1}, { -2, -1}, { 1, 2}, { 1, -2}, { -1, 2}, { -1, -2}};
    public int[][] tourOfKnight(int m, int n, int r, int c) {
        int[][] result = new int[m][n];
        for (int i = 0; i < m; i++) {
            Arrays.fill(result[i], -1);
        }
        dfs(m, n, r, c, result, 0);
        return result;
    }
    private boolean dfs(int m, int n, int r, int c, int[][] result, int order) {
        if (r >= m || r < 0 || c >= n || c < 0 || result[r][c] != -1) {
            return false;
        }
        if (order == m*n-1) {
            result[r][c] = order;
            return true;
        }
            
        result[r][c] = order;
        for (int[] dir: DIRS) {
            if (dfs(m, n, r + dir[0], c + dir[1], result, order+1)) {
                return true;
            }
        }
        result[r][c] = -1;
        return false;
    }
}

/**

T: O((mn)^7)

https://leetcode.com/problems/the-knights-tour/solutions/3486149/java-dfs-w-memo-solution/
 */
```
````
