2596.检查骑士巡视方案

链接：2596.检查骑士巡视方案
难度：Medium
标签：深度优先搜索、广度优先搜索、数组、矩阵、模拟
简介：如果 grid 表示了骑士的有效巡视方案，返回 true；否则返回 false。

题解 1 - cpp

• 编辑时间：2023-03-19
• 执行用时：8ms
• 内存消耗：27MB
• 编程语言：cpp
• 解法介绍：从0到末尾，用方向数组遍历所有数。

int dirs[8][2] = {
    {-2, -1}, {-1, -2},
    {-2, 1}, {-1, 2},
    {1, -2}, {2, -1},
    {1, 2}, {2, 1},
};
class Solution {
public:
    typedef pair<int, int> pii;
    bool checkValidGrid(vector<vector<int>>& grid) {
        int n = grid.size();
        pii cur = make_pair(0,0);
        for (int i = 0; i < n * n; i++) {
            if (grid[cur.first][cur.second] != i) return false;
            for (int j = 0; j < 8; j++) {
                int nrow = cur.first + dirs[j][0], ncol = cur.second + dirs[j][1];
                if (nrow < 0 || nrow >= n || ncol < 0 || ncol >= n) continue;
                if (grid[nrow][ncol] == i + 1) {
                    cur = make_pair(nrow, ncol);
                    break;
                }
            }
        }
        return true;
    }
};

题解 2 - python

• 编辑时间：2023-03-19
• 执行用时：32ms
• 内存消耗：15MB
• 编程语言：python
• 解法介绍：同上。

class Solution:
    def checkValidGrid(self, grid: List[List[int]]) -> bool:
        dirs = [
            [-2, -1], [-1, -2],
            [-2, 1], [-1, 2],
            [1, -2], [2, -1],
            [1, 2], [2, 1],
        ]
        n = len(grid)
        cur = (0, 0)
        for i in range(n*n):
            if grid[cur[0]][cur[1]] != i:
                return False
            for j in range(8):
                nrow, ncol = cur[0] + dirs[j][0], cur[1]+dirs[j][1]
                if 0 <= nrow < n and 0 <= ncol < n and grid[nrow][ncol] == i + 1:
                    cur = (nrow, ncol)
                    break
        return True

题解 3 - rust

• 编辑时间：2023-03-19
• 执行用时：4ms
• 内存消耗：1.9MB
• 编程语言：rust
• 解法介绍：同上。

impl Solution {
    pub fn check_valid_grid(grid: Vec<Vec<i32>>) -> bool {
        const dirs: [[i32; 2]; 8] = [
            [-2, -1],
            [-1, -2],
            [-2, 1],
            [-1, 2],
            [1, -2],
            [2, -1],
            [1, 2],
            [2, 1],
        ];
        let n = grid.len();
        let mut cur = (0, 0);
        for i in 0..n * n {
            if grid[cur.0][cur.1] != i as i32 {
                return false;
            }
            for dir in dirs {
                let (nrow, ncol) = (cur.0 as i32 + dir[0], cur.1 as i32 + dir[1]);
                if nrow >= 0
                    && (nrow as usize) < n
                    && ncol >= 0
                    && (ncol as usize) < n
                    && grid[nrow as usize][ncol as usize] == i as i32 + 1
                {
                    cur = (nrow as usize, ncol as usize);
                    break;
                }
            }
        }
        true
    }
}

题解 4 - python

• 编辑时间：2023-09-13
• 执行用时：40ms
• 内存消耗：16MB
• 编程语言：python
• 解法介绍：遍历。

dirs = [(1, 2), (1, -2), (2, 1), (2, -1), (-1, 2), (-1, -2), (-2, 1), (-2, -1)]
class Solution:
    def checkValidGrid(self, grid: List[List[int]]) -> bool:
        n = len(grid)
        cur = (0, 0)
        if grid[0][0] != 0: return False
        for i in range(n * n - 1):
            f = False
            for dir in dirs:
                x = cur[0] + dir[0]
                y = cur[1] + dir[1]
                if 0 <= x < n and 0 <= y < n and grid[x][y] == i + 1:
                    f = True
                    cur = (x, y)
            if not f:
                return False
        return True