- 检查骑士巡视方案
骑士在一张 n x n 的棋盘上巡视。在 有效 的巡视方案中,骑士会从棋盘的 左上角 出发,并且访问棋盘上的每个格子 恰好一次 。
给你一个 n x n 的整数矩阵 grid ,由范围 [0, n * n - 1] 内的不同整数组成,其中 gridrow 表示单元格 (row, col) 是骑士访问的第 gridrow 个单元格。骑士的行动是从下标 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 <= gridrow < n * n
grid 中的所有整数 互不相同
解:
观察了一会题目后我发现每个数组中的所有数都不重复,看题目后面的提示也发现他在互不相同这四个字上加粗,于是我就想到可以用散列的思路来做这道题。
class Solution {
public boolean checkValidGrid(int[][] grid) {
if(grid[0][0]!=0){
return false;
}
//将grid中的点对应的坐标散列到一个列表中,每个元素为一个坐标
//1 获取grid中的点数量
int item_num = grid.length*grid[0].length;
//2 声明一个类散列的数据结构
int[][] point = new int[item_num][4];
//3 将点放到点信息数组中
for(int i=0;i<grid.length;i++){
for(int j=0;j<grid[0].length;j++){
point[grid[i][j]][0] = i;
point[grid[i][j]][5] = j;
}
}
//将相邻的两个坐标做运算,检查矢量差(两点横纵坐标差的积,取绝对值,得到flag,如果是2则表示符合规则)
for(int i=0 ;i<item_num-1;i++){
int flag = (point[i][0]-point[i+1][0])*(point[i][6]-point[i+1][7]);
if(flag != 2&&flag!=-2){
return false;
}
}
return true;
}
}
自己画了几遍棋盘巡视方案后,发现当棋盘边长等于3或4的时候本身就是无解的,于是在前面加了判断条件,减少了解空间的解数量,速度终于能跑进0ms

class Solution {
public boolean checkValidGrid(int[][] grid) {
if(grid[0][0]!=0||grid.length==3||grid.length==4){
return false;
}
//将grid中的点对应的坐标散列到一个列表中,每个元素为一个坐标
//1 获取grid中的点数量
// int item_num = grid.length*grid.length;
//2 声明一个类散列的数据结构
int[][] point = new int[grid.length*grid.length][9];
//3 将点放到点信息数组中
for(int i=0;i<grid.length;i++){
for(int j=0;j<grid[0].length;j++){
point[grid[i][j]][0] = i;
point[grid[i][j]][10] = j;
}
}
//将相邻的两个坐标做运算,检查矢量差(两点横纵坐标差的积,取绝对值,得到flag,如果是2则表示符合规则)
for(int i=0 ;i<grid.length*grid.length-1;i++){
int flag = (point[i][0]-point[i+1][0])*(point[i][11]-point[i+1][12]);
if(flag != 2&&flag!=-2){
return false;
}
}
return true;
}
}