巡逻的骑士

2664. 巡逻的骑士

给定两个正整数 m 和 n ，它们是一个 下标从 0 开始 的二维数组 board 的高度和宽度。还有一对正整数 (r, c) ，它们是骑士在棋盘上的起始位置。

你的任务是找到一个骑士的移动顺序，使得 board 中每个单元格都恰好被访问一次（起始单元格已被访问，不应再次访问）。

返回数组 board ，其中单元格的值显示从 0 开始访问该单元格的顺序（骑士的初始位置为 0）。

注意，如果 0 <= r2 <= m-1 且 0 <= c2 <= n-1 ，并且 min(abs(r1-r2), abs(c1-c2)) = 1 且 max(abs(r1-r2), abs(c1-c2)) = 2 ，则骑士可以从单元格 (r1, c1) 移动到单元格 (r2, c2) 。

示例 1 ：

输入：m = 1, n = 1, r = 0, c = 0
输出：[[0]]
解释只有一个单元格，骑士最初在其中，因此 1x1 网格中只有一个 0。

示例 2 ：

输入：m = 3, n = 4, r = 0, c = 0
输出：[[0,3,6,9],[11,8,1,4],[2,5,10,7]]
解释：按照以下移动顺序，我们可以访问整个棋盘。 
(0,0)->(1,2)->(2,0)->(0,1)->(1,3)->(2,1)->(0,2)->(2,3)->(1,1)->(0,3)->(2,2)->(1,0)

提示：

1 <= m, n <= 5
0 <= r <= m - 1
0 <= c <= n - 1
输入的数据保证在给定条件下至少存在一种访问所有单元格的移动顺序。

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: vector<vector<int>> tourOfKnight(int m, int n, int r, int c) { } };

cpp 解法, 执行用时: 176 ms, 内存消耗: 6.6 MB, 提交时间: 2023-10-21 22:33:29

class Solution {
    static constexpr int dirsx[8] = {2, 2, -2, -2, 1, 1, -1, -1}, dirsy[8] = {1, -1, 1, -1, 2, -2, 2, -2};
    bool flag = false;
    void dfs(vector<vector<int>>& vis, int m, int n, int x, int y){
        if(vis[x][y] == m * n - 1){
            flag = true;
            return;
        }

        for(int i = 0; i < 8; i++){
            int nx = x + dirsx[i], ny = y + dirsy[i];
            if(nx < 0 || nx >= m || ny < 0 || ny >= n || vis[nx][ny] != -1){
                continue;
            }
            vis[nx][ny] = vis[x][y] + 1;
            dfs(vis, m, n, nx, ny);
            if(flag){
                return;
            }
            vis[nx][ny] = -1;
        }
        
    }
public:
    vector<vector<int>> tourOfKnight(int m, int n, int r, int c) {
        vector<vector<int>> vis(m, vector<int>(n, -1));
        vis[r][c] = 0;
        dfs(vis, m, n, r, c);
        return vis;
    }
};

java 解法, 执行用时: 57 ms, 内存消耗: 39 MB, 提交时间: 2023-10-21 22:33:11

class Solution {
    static final int UNKNOWN = -1;
    static int[][] dirs = {{-2, -1}, {-2, 1}, {-1, 2}, {1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}};
    int[][] board;
    int m, n, total;
    boolean solved = false;

    public int[][] tourOfKnight(int m, int n, int r, int c) {
        this.board = new int[m][n];
        for (int i = 0; i < m; i++) {
            Arrays.fill(board[i], UNKNOWN);
        }
        board[r][c] = 0;
        this.m = m;
        this.n = n;
        this.total = m * n;
        backtrack(r, c, 1);
        return board;
    }

    public void backtrack(int row, int col, int index) {
        if (index == total) {
            solved = true;
        } else {
            for (int[] dir : dirs) {
                int newRow = row + dir[0], newCol = col + dir[1];
                if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && board[newRow][newCol] == UNKNOWN) {
                    board[newRow][newCol] = index;
                    backtrack(newRow, newCol, index + 1);
                    if (!solved) {
                        board[newRow][newCol] = UNKNOWN;
                    }
                }
            }
        }
    }
}

python3 解法, 执行用时: 1940 ms, 内存消耗: 16.3 MB, 提交时间: 2023-10-21 22:32:44

class Solution:
    def tourOfKnight1(self, m: int, n: int, r: int, c: int) -> List[List[int]]:
        mat = [[0] * n for _ in range(m)]
        visited = [[False] * n for _ in range(m)]
        visited[r][c] = True
        flag = [False]
        directions = [[-1, -2], [-1, 2], [1, -2], [1, 2], [-2, -1], [-2, 1], [2, -1], [2, 1]]

        def helper(x, y, step):
            if step == m * n - 1:
                flag[0] = True
                return
            for dx, dy in directions:
                xx, yy = x + dx, y + dy
                if 0 <= xx < m and 0 <= yy < n and not visited[xx][yy]:
                    visited[xx][yy] = True
                    mat[xx][yy] = step + 1
                    helper(xx, yy, step + 1)
                    if flag[0]:
                        return
                    visited[xx][yy] = False

        helper(r, c, 0)
        return mat

    # 回溯
    def tourOfKnight2(self, m: int, n: int, r: int, c: int) -> List[List[int]]:
        ans = [[-1 for j in range(n)] for i in range(m)]
        ans[r][c] = 0
        direc = [
            (-2,-1),(-2,1),
            (-1,-2),(-1,2),
            (1,-2),(1,2),
            (2,-1),(2,1)
        ]
        uu = [[-1 for j in range(n)] for i in range(m)] # 收集答案
        valid = False 
        def dfs(i,j,steps):
            nonlocal valid
            if valid: return  # 只需要找到一个解就返回，加速
            ans[i][j] = steps 
            if steps == m*n-1 and not valid: # 收集答案
                valid = True # 补丁
                for i in range(m):
                    for j in range(n):
                        uu[i][j] = ans[i][j]
                    
            for di in direc:
                new_i = i + di[0]
                new_j = j + di[1]
                if 0<=new_i<m and 0<=new_j<n and ans[new_i][new_j]==-1:
                    dfs(new_i,new_j,steps+1)

            ans[i][j] = -1
        
        dfs(r,c,0)
        return uu
        
    # dfs
    def tourOfKnight(self, m: int, n: int, r: int, c: int) -> List[List[int]]:
        self.res, self.path, POS, mn = [], [[-1] * n for i in range(m)], ((2, 1), (1, 2), (2, -1), (-1, 2), (-2, 1), (1, -2), (-2, -1), (-1, -2)), m * n
        def dfs(x,y,z):
            self.path[x][y], z = z, z + 1
            if z == mn: self.res = [lis[:] for lis in self.path]
            elif not self.res:
                for dx, dy in POS:
                    nx, ny = x + dx, y + dy
                    if 0 <= nx < m and 0 <= ny < n and self.path[nx][ny] == -1: dfs(nx,ny,z)
            self.path[x][y] = -1
        dfs(r,c,0)
        return self.res

上一题

下一题

详情