检查骑士巡视方案【LC2596】
骑士在一张 n x n 的棋盘上巡视。在有效的巡视方案中，骑士会从棋盘的 左上角 出发，并且访问棋盘上的每个格子 恰好一次 。
给你一个 n x n 的整数矩阵 grid ，由范围 [0, n * n - 1] 内的不同整数组成，其中 grid[row][col] 表示单元格 (row, col) 是骑士访问的第 grid[row][col] 个单元格。骑士的行动是从下标 0 开始的。
如果 grid 表示了骑士的有效巡视方案，返回 true；否则返回 false。
注意，骑士行动时可以垂直移动两个格子且水平移动一个格子，或水平移动两个格子且垂直移动一个格子。下图展示了骑士从某个格子出发可能的八种行动路线。
思路：
将每个单元格位置和值组成的三元组放入小顶堆中，保证按顺序移动。
首先需要判断起点是否位于左上角，否则直接返回false【因为这个WA了】
然后判断能否移动至下一个位置，根据横纵坐标的差值判断，差值的可能性有八种，如果符合任意一种则移动至下一个位置，否则返回false
如果可以移动至最后一个节点，那么返回true
实现
class Solution { public boolean checkValidGrid(int[][] grid) { int n = grid.length; // 存储三元组 PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o1[2] - o2[2]); for (int i = 0; i < n; i++){ for (int j = 0; j < n; j++){ pq.add(new int[]{i, j, grid[i][j]}); } } // 判断起点 int[] pre = pq.poll(); if (pre[0] != 0 || pre[1] != 0) return false; while (!pq.isEmpty()){ int[] next = pq.poll(); int[] move = {next[0] - pre[0], next[1] - pre[1]}; // 判断能否移动至下一个位置 if (!isCorrect(move)){ return false; } pre = next; } return true; } public boolean isCorrect(int[] move){ int[] d1 = {2, -2}; int[] d2 = {1, -1}; for (int i = 0; i < 2; i++){ for (int j = 0; j < 2;j++){ if (move[0] == d1[i] && move[1] == d2[j]){ return true; } if (move[0] == d2[i] && move[1] == d1[j]){ return true; } } } return false; } }
复杂度
时间复杂度：O(n^2)
空间复杂度：O(n^2)
