检查骑士巡视方案

难度: Medium

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

Submission

运行时间: 26 ms

内存: 16.0 MB

class Solution:
    def checkValidGrid(self, grid: List[List[int]]) -> bool:
        n = len(grid)
        a = []
        if grid[0][0] != 0:
            return False
        for i in range(n):
            for j in range(n):
                a.append([i,j,grid[i][j]])
        a.sort(key = lambda x:x[2])
        for i in range(1, len(a)):
            if (abs(a[i][0] - a[i-1][0]) == 2 and abs(a[i][1] - a[i-1][1]) == 1) or (abs(a[i][0] - a[i-1][0]) == 1 and abs(a[i][1] - a[i-1][1]) == 2):
                continue
            else:
                return False
        return True

Explain

该题解首先检查骑士是否从棋盘的左上角（即位置grid[0][0]）开始。然后，它创建一个列表a来存储棋盘上每个单元格的行坐标、列坐标和访问顺序编号。列表a按访问顺序编号排序，使得可以按骑士访问的实际顺序检查每一步的行动是否有效。对于列表a中的每一对连续单元格，检查它们是否符合骑士移动的规则：垂直移动两格且水平移动一格，或水平移动两格且垂直移动一格。如果所有连续单元格都符合骑士的移动规则，则返回true，否则返回false。

时间复杂度: O(n^2 log n)

空间复杂度: O(n^2)

class Solution:
    def checkValidGrid(self, grid: List[List[int]]) -> bool:
        n = len(grid)
        a = []
        # 首先检查是否从左上角开始
        if grid[0][0] != 0:
            return False
        # 创建列表a，存储每个单元格的行、列和访问编号
        for i in range(n):
            for j in range(n):
                a.append([i,j,grid[i][j]])
        # 根据访问顺序对列表a进行排序
        a.sort(key = lambda x:x[2])
        # 检查每一步移动是否满足骑士的移动规则
        for i in range(1, len(a)):
            if (abs(a[i][0] - a[i-1][0]) == 2 and abs(a[i][1] - a[i-1][1]) == 1) or (abs(a[i][0] - a[i-1][0]) == 1 and abs(a[i][1] - a[i-1][1]) == 2):
                continue
            else:
                return False
        return True

Explore

首先检查骑士是否从棋盘的左上角开始是为了确保骑士的巡视方案遵循特定的起始规则。在很多情况下，开始位置对于解决问题是关键的，特别是在路径或巡游问题中，起始点的设定能够影响到整个解决方案的可行性与正确性。如果骑士不从左上角开始，可能就违反了题目设定的巡视起始条件，因此这一检查是确保所有后续逻辑建立在正确的前提上。

使用列表a来存储每个单元格的行、列和访问顺序编号的优势在于能够更为灵活地处理和排序数据。通过对列表a进行排序，可以便捷地按照访问顺序检查骑士的移动是否合法，而不需要在原矩阵上进行复杂的索引操作和状态追踪。然而，这种方法的劣势在于需要额外的空间来存储相同的数据，并且涉及额外的数据结构处理，如排序操作，这可能增加算法的时间复杂度。

题解中的方法确保了每一步移动都符合骑士的移动规则，但实际上并没有直接提及对棋盘边界的处理。鉴于题解是基于每对连续单元格（由访问顺序决定）进行骑士移动规则的验证，只要这些单元格的坐标都在棋盘内，就隐含地满足了边界条件。因此，只要访问顺序是正确的，棋盘边界自然得到了处理。