2596-检查骑士巡视方案

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:29 2023-09-13 16:06:29 Updated    

骑士在一张 n x n 的棋盘上巡视。在有效的巡视方案中，骑士会从棋盘的 左上角 出发，并且访问棋盘上的每个格子 恰好一次 。

给你一个 n x n 的整数矩阵 grid ，由范围 [0, n * n - 1] 内的不同整数组成，其中 grid[row][col]
表示单元格 (row, col) 是骑士访问的第 grid[row][col] 个单元格。骑士的行动是从下标 0 开始的。

如果 grid 表示了骑士的有效巡视方案，返回 true；否则返回 false。

注意 ，骑士行动时可以垂直移动两个格子且水平移动一个格子，或水平移动两个格子且垂直移动一个格子。下图展示了骑士从某个格子出发可能的八种行动路线。

示例 1：

**输入：** grid = [[0,11,16,5,20],[17,4,19,10,15],[12,1,8,21,6],[3,18,23,14,9],[24,13,2,7,22]]
**输出：** true
**解释：** grid 如上图所示，可以证明这是一个有效的巡视方案。

示例 2：

**输入：** grid = [[0,3,6],[5,8,1],[2,7,4]]
**输出：** false
**解释：** grid 如上图所示，考虑到骑士第 7 次行动后的位置，第 8 次行动是无效的。

提示：

  • n == grid.length == grid[i].length
  • 3 <= n <= 7
  • 0 <= grid[row][col] < n * n
  • grid 中的所有整数 互不相同

方法一：直接模拟

题目要求骑士的移动的每一步均按照「日」字形跳跃，假设从位置 (x_1, y_1) 跳跃到 (x_2, y_2)，则此时一定满足下面两种情形之一：

  • |x_1 - x_2| = 1, |y_1 - y_2| = 2；
  • |x_1 - x_2| = 2, |y_1 - y_2| = 1。

设矩阵的长度为 n，其中 grid}[\textit{row}][\textit{col}] 表示单元格 (\textit{row}, \textit{col}) 是骑士访问的第 grid}[\textit{row}][\textit{col}] 个单元格，因此可以知道每个单元格的访问顺序，我们用 indices 存储单元格的访问顺序，其中 indices}[i] 表示骑士在经过第 i-1 次跳跃后的位置。由于骑士的行动是从下标 0 开始的，因此一定需要满足 grid}[0][0] = 0，接下来依次遍历 indices 中的每个元素。由于 indices}[i] 是一次跳跃的起点，indices}[i+1] 是该次跳跃的终点，则依次检测每一次跳跃的行动路径是否为「日」字形，即满足如下条件：

  • |\textit{indices}[i][0] - \textit{indices}[i+1][0]| = 1, |\textit{indices}[i][1] - \textit{indices}[i+1][1]| = 2；
  • |\textit{indices}[i][0] - \textit{indices}[i+1][0]| = 2, |\textit{indices}[i][1] - \textit{indices}[i+1][1]| = 1。

为了方便计算，我们只需检测 |x_1 - x_2| \times |y_1 - y_2| 是否等于 2 即可。如果所有跳跃路径均合法则返回 true，否则返回 false。

思路与算法

代码

[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    bool checkValidGrid(vector<vector<int>>& grid) {
        if (grid[0][0] != 0) {
            return false;
        }
        int n = grid.size();
        vector<array<int, 2>> indices(n * n);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                indices[grid[i][j]] = {i, j};
            }
        }
        for (int i = 1; i < indices.size(); i++) {
            int dx = abs(indices[i][0] - indices[i - 1][0]);
            int dy = abs(indices[i][1] - indices[i - 1][1]);
            if (dx * dy != 2) {
                return false;
            }
        }
        return true;
    }
};
[sol1-C]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
bool checkValidGrid(int** grid, int gridSize, int* gridColSize) {
    if (grid[0][0] != 0) {
        return false;
    }
    int n = gridSize;
    int indices[n * n][2];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            indices[grid[i][j]][0] = i;
            indices[grid[i][j]][1] = j;
        }
    }
    for (int i = 1; i < n * n; i++) {
        int dx = abs(indices[i][0] - indices[i - 1][0]);
        int dy = abs(indices[i][1] - indices[i - 1][1]);
        if (dx * dy != 2) {
            return false;
        }
    }
    return true;
}
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public boolean checkValidGrid(int[][] grid) {
        if (grid[0][0] != 0) {
            return false;
        }
        int n = grid.length;
        int[][] indices = new int[n * n][2];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                indices[grid[i][j]][0] = i;
                indices[grid[i][j]][1] = j;
            }
        }
        for (int i = 1; i < n * n; i++) {
            int dx = Math.abs(indices[i][0] - indices[i - 1][0]);
            int dy = Math.abs(indices[i][1] - indices[i - 1][1]);
            if (dx * dy != 2) {
                return false;
            }
        }
        return true;
    }
}
[sol1-C#]
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
public class Solution {
    public bool CheckValidGrid(int[][] grid) {
        if (grid[0][0] != 0) {
            return false;
        }
        int n = grid.Length;
        int[][] indices = new int[n * n][];
        for (int i = 0; i < n * n; i++) {
            indices[i] = new int[2];
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                indices[grid[i][j]][0] = i;
                indices[grid[i][j]][1] = j;
            }
        }
        for (int i = 1; i < n * n; i++) {
            int dx = Math.Abs(indices[i][0] - indices[i - 1][0]);
            int dy = Math.Abs(indices[i][1] - indices[i - 1][1]);
            if (dx * dy != 2) {
                return false;
            }
        }
        return true;
    }
}
[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def checkValidGrid(self, grid: List[List[int]]) -> bool:
        if grid[0][0] != 0:
            return False
        n = len(grid)
        indices = [[] for _ in range(n * n)]
        for i in range(n):
            for j in range(n):
                indices[grid[i][j]] = [i, j]
        for i in range(1, n * n, 1):
            dx = abs(indices[i][0] - indices[i - 1][0])
            dy = abs(indices[i][1] - indices[i - 1][1])
            if dx * dy != 2:
                return False
        return True
[sol1-Go]
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
28
func checkValidGrid(grid [][]int) bool {
    if grid[0][0] != 0 {
        return false;
    }
    n := len(grid)
    indices := make([][2]int, n * n)
    for i := 0; i < n; i++ {
        for j := 0; j < n; j++ {
            indices[grid[i][j]][0] = i;
            indices[grid[i][j]][1] = j;
        }
    }
    for i := 1; i < n * n; i++ {
        dx := abs(indices[i][0] - indices[i - 1][0])
        dy := abs(indices[i][1] - indices[i - 1][1])
        if dx * dy != 2 {
            return false
        }
    }
    return true
}

func abs(x int) int { 
    if x < 0 { 
        return -x 
    }
    return x 
}
[sol1-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
var checkValidGrid = function(grid) {
    if (grid[0][0] != 0) {
        return false;
    }
    const n = grid.length;
    let indices = Array(n * n).fill().map(() => Array(2));
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            indices[grid[i][j]][0] = i;
            indices[grid[i][j]][1] = j;
        }
    }
    for (let i = 1; i < n * n; i++) {
        let dx = Math.abs(indices[i][0] - indices[i - 1][0]);
        let dy = Math.abs(indices[i][1] - indices[i - 1][1]);
        if (dx * dy != 2) {
            return false;
        }
    }
    return true;
};

复杂度分析

  • 时间复杂度：O(n^2)，其中 n 表示二维棋盘边的长度。需要检测棋盘中的每个位置，一共需要检测 n^2 个位置，因此时间复杂度为 O(n^2)。

  • 空间复杂度：O(n^2)，其中 n 表示二维棋盘边的长度。用来需要存放每个位置的访问顺序，一共有 n^2 个位置，需要的空间为 O(n^2)。

 Comments
On this page
2596-检查骑士巡视方案