2596. 检查骑士巡视方案

难度: 中等

来源: 每日一题 2023.09.13

---

骑士在一张 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 中的所有整数 互不相同

class Solution {
    public boolean checkValidGrid(int[][] grid) {

    }
}

分析与题解

---

• HashMap + 向量的距离

  这个题目的解题关键是怎么知道, 我们可以去往下一个点? 这个很简单, 我们判断一下当前节点和下一个节点是一个 日 字形状即可. 那么表现形式是什么呢? 也就是 x 方向的距离 和 y 方向的距离 乘积为 2

  知道上面的条件, 我们首先处理边界条件, 也就是说我们必须从 左上角 开始巡逻.

  if (grid[0][0] != 0) {
      return false;
  }
  

  然后查找所有点的位置, 并且进行存储.

  // 先查找所有点的位置
  Map<Integer, Integer[]> cache = new HashMap<>();
  for(int i = 0; i < grid.length; i++) {
      int[] group = grid[i];
      for(int j = 0; j < group.length; j++) {
          cache.put(grid[i][j], new Integer[]{i, j});
      }
  }
  

  构建好完整的HashMap , 我么就遍历所有的节点. 判断当前节点和下一个节点是否满足距离要求. 如果不满足就直接 return false;

  int count =  cache.keySet().size() - 1;
  for(int i = 0; i < count; i++) {
      Integer[] firstGroup = cache.get(i);
      Integer[] secondGroup = cache.get(i + 1);
      int x = Math.abs(firstGroup[0] - secondGroup[0]);
      int y = Math.abs(firstGroup[1] - secondGroup[1]);
      // 判断向量之间的距离即可
      if (x * y != 2) {
          return false;
      }
  }
  

  如果查找到最后仍然符合条件. 那也就是整个矩阵的点都能巡逻到, 符合题意, 返回 true 即可.

  
  

  接下来, 我们一起看下完整的解题过程.

  class Solution {
      public boolean checkValidGrid(int[][] grid) {
          if (grid[0][0] != 0) {
              return false;
          }
          // 先查找所有点的位置
          Map<Integer, Integer[]> cache = new HashMap<>();
          for(int i = 0; i < grid.length; i++) {
              int[] group = grid[i];
              for(int j = 0; j < group.length; j++) {
                  cache.put(grid[i][j], new Integer[]{i, j});
              }
          }
          // 遍历查找点是否合适 从 0 查到 cache.keySet().size() - 1 - 1, 最后一个点不用查
          int count =  cache.keySet().size() - 1;
          for(int i = 0; i < count; i++) {
              Integer[] firstGroup = cache.get(i);
              Integer[] secondGroup = cache.get(i + 1);
              int x = Math.abs(firstGroup[0] - secondGroup[0]);
              int y = Math.abs(firstGroup[1] - secondGroup[1]);
              // 判断向量之间的距离即可
              if (x * y != 2) {
                  return false;
              }
          }
          return true;
      }
  }
  

  
  

  复杂度分析:

  • 时间复杂度: O(n² + n), 需要遍历矩阵,所以时间复杂度为 n², 然后再遍历一遍HashMap.
  • 空间复杂度: O(n²)，HashMap的空间开辟与矩阵的空间大小成线性关系.

  结果如下所示.