题目描述：

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

解法一：模拟

算法思路：

根据题意可知，骑士正确的移动应为 日 字形，假设从位置（x1, y1）跳到（x2, y2）,则应该满足以下两种情形之一：

• $$ |x1 – x2| = 1, |y1 – y2| = 2 $$

• $$ |x1 – x2| = 2, |y1 – y2| = 1 $$

假设 geid 的长度为 n，我们可以：

• 定义一个数组 pos[n * n] [2]，用于记录骑士依次跳跃的坐标位置。
• 判断两次跳跃是否符合 日 字形，即计算∣x1−x2∣×∣y1−y2∣ 是否等于 2。
• 如果所有跳跃路径都合法则返回 true，否则返回 false。

代码实现：

class Solution {
    public boolean checkValidGrid(int[][] grid) {
        // 如果起点不是左上角，直接返回false
        if (grid[0][0] != 0){
            return false;
        }

        // 记录每次跳跃的坐标
        int n = grid.length;
        int [][] pos = new int[n * n][2];
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                pos[grid[i][j]] = new int[] {i, j};
            }
        }
        // 判断两次跳跃是否是日字形，即|x1 - x2| * |y1 - y2| 是否等于2
        for(int i = 1; i < n*n ;i++){
            int dx = Math.abs(pos[i][0] - pos[i - 1][0]);
            int dy = Math.abs(pos[i][1] - pos[i - 1][1]);
            if(dx * dy != 2){
                return false;
            }
        }
        return true;
    }
}

复杂度分析：

时间复杂度： O(n ^ 2)，其中 n 表示二维棋盘边的长度。需要检测棋盘中的每个位置，一共需要检测 n^2 个位置

空间复杂度： O(n ^ 2)，其中 n 表示二维棋盘边的长度。用来需要存放每个位置的访问顺序，一共有 n^2 个位置

相关链接

• 2596. 检查骑士巡视方案