重庆网站建设公司那好,江苏元鼎建设工程有限公司网站,滨州做网站建设的公司,wordpress wind2596. 检查骑士巡视方案 骑士在一张 n x n 的棋盘上巡视。在 有效 的巡视方案中#xff0c;骑士会从棋盘的 左上角 出发#xff0c;并且访问棋盘上的每个格子 恰好一次 。 给你一个 n x n 的整数矩阵 grid #xff0c;由范围 [0, n * n - 1] 内的不同整数组成#xff0c;其… 2596. 检查骑士巡视方案 骑士在一张 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].length3 n 70 grid[row][col] n * ngrid 中的所有整数 互不相同 思路
初始为xy 每一次移动后是一个x1 y1 |(x1-x)*(y1-y)| 一定为2所以就出来了
用表示1的位置与0的位置此方法进行计算 然后2对应的x2 y2索引与1.......全部满足就返回true
但是0 到1到2...的数字位置不知道所以这时候用一个容器进行排序。具体看题解
class Solution {
public:bool checkValidGrid(vectorvectorint grid) {if(grid[0][0]!0) //如果骑士不在(0,0)的位置返回false{return false;}int ngrid.size();vectorarrayint,2 arr(n*n);//定义一个n*n的容器 其中每个元素都是长度为2的数组for(int i0;in;i){for(int j0;jn;j){arr[grid[i][j]]{i,j}; //将0到n*n的对应的索引放在容器中。}} for(int i1;in*n;i){if(abs(arr[i][0]-arr[i-1][0])*abs(arr[i][1]-arr[i-1][1])!2) //因为开始的位置与移动 //后的位置一定是 一个1*2的长方形对角 //绝对值的差值为2return false;} return true;}
};
