本文最后更新于 389 天前,其中的信息可能已经有所发展或是发生改变。
题目描述:
骑士在一张 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
中的所有整数 互不相同
解法一:模拟
算法思路:
根据题意可知,骑士正确的移动应为 日 字形,假设从位置(x1, y1)跳到(x2, y2),则应该满足以下两种情形之一:
-
$$ |x1 – x2| = 1, |y1 – y2| = 2 $$
-
$$ |x1 – x2| = 2, |y1 – y2| = 1 $$
假设 geid
的长度为 n,我们可以:
- 定义一个数组 pos[n * n] [2],用于记录骑士依次跳跃的坐标位置。
- 判断两次跳跃是否符合 日 字形,即计算∣x1−x2∣×∣y1−y2∣ 是否等于 2。
- 如果所有跳跃路径都合法则返回 true,否则返回 false。
代码实现:
class Solution {
public boolean checkValidGrid(int[][] grid) {
// 如果起点不是左上角,直接返回false
if (grid[0][0] != 0){
return false;
}
// 记录每次跳跃的坐标
int n = grid.length;
int [][] pos = new int[n * n][2];
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
pos[grid[i][j]] = new int[] {i, j};
}
}
// 判断两次跳跃是否是日字形,即|x1 - x2| * |y1 - y2| 是否等于2
for(int i = 1; i < n*n ;i++){
int dx = Math.abs(pos[i][0] - pos[i - 1][0]);
int dy = Math.abs(pos[i][1] - pos[i - 1][1]);
if(dx * dy != 2){
return false;
}
}
return true;
}
}
复杂度分析:
时间复杂度: O(n ^ 2),其中 n 表示二维棋盘边的长度。需要检测棋盘中的每个位置,一共需要检测 n^2 个位置
空间复杂度: O(n ^ 2),其中 n 表示二维棋盘边的长度。用来需要存放每个位置的访问顺序,一共有 n^2 个位置