- 检查骑士巡视方案
骑士在一张 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;
}
}
本文由 ice 创作，采用 知识共享署名4.0 国际许可协议进行许可。
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名。