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
解释：上面的图代表网格。可以证明这是一个有效的配置。

示例 2：

输入：grid = [[0,3,6],[5,8,1],[2,7,4]]
输出：false
解释：上面的图代表网格。骑士第8步的移动对于其在第7步之后的位置来说是无效的。

提示：

  • n == grid.length == grid[i].length
  • 3 <= n <= 7
  • 0 <= grid[row][col] < n * n
  • grid 中的所有整数都不相同

解题思路

这道题需要验证给定的网格是否表示了一个有效的骑士巡游路径。

解题思路：

  1. 建立位置映射：首先需要建立从移动步数到位置坐标的映射关系。遍历网格，将每个位置的步数作为key，位置坐标作为value存储起来。

  2. 验证起始位置：骑士必须从左上角（0,0）开始，所以需要检查步数为0的位置是否在（0,0）。

  3. 验证移动有效性：从步数0开始，依次检查每一步移动是否符合骑士的移动规则。骑士的移动规则是：水平移动2格+垂直移动1格，或者水平移动1格+垂直移动2格。

  4. 骑士移动的8个方向：定义8个可能的移动方向：[(2,1), (2,-1), (-2,1), (-2,-1), (1,2), (1,-2), (-1,2), (-1,-2)]

  5. 逐步验证：对于每一步i（从0到n²-2），检查从位置i到位置i+1的移动是否是有效的骑士移动。

算法流程：

  • 创建位置映射表
  • 检查起始位置是否为（0,0）
  • 遍历所有相邻步数，验证移动的有效性
  • 如果所有移动都有效，返回true；否则返回false

时间复杂度分析： O(n²) - 需要遍历所有格子建立映射，然后验证n²-1次移动 空间复杂度分析： O(n²) - 存储位置映射表

代码实现

class Solution {
public:
    bool checkValidGrid(vector<vector<int>>& grid) {
        int n = grid.size();
        vector<pair<int, int>> positions(n * n);
        
        // 建立从步数到位置的映射
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                positions[grid[i][j]] = {i, j};
            }
        }
        
        // 检查起始位置是否为(0,0)
        if (positions[0] != make_pair(0, 0)) {
            return false;
        }
        
        // 骑士的8个可能移动方向
        vector<pair<int, int>> moves = {{2,1}, {2,-1}, {-2,1}, {-2,-1}, {1,2}, {1,-2}, {-1,2}, {-1,-2}};
        
        // 检查每一步移动是否有效
        for (int i = 0; i < n * n - 1; i++) {
            auto [x1, y1] = positions[i];
            auto [x2, y2] = positions[i + 1];
            
            bool validMove = false;
            for (auto [dx, dy] : moves) {
                if (x1 + dx == x2 && y1 + dy == y2) {
                    validMove = true;
                    break;
                }
            }
            
            if (!validMove) {
                return false;
            }
        }
        
        return true;
    }
};

class Solution:
    def checkValidGrid(self, grid: List[List[int]]) -> bool:
        n = len(grid)
        positions = [None] * (n * n)
        
        # 建立从步数到位置的映射
        for i in range(n):
            for j in range(n):
                positions[grid[i][j]] = (i, j)
        
        # 检查起始位置是否为(0,0)
        if positions[0] != (0, 0):
            return False
        
        # 骑士的8个可能移动方向
        moves = [(2,1), (2,-1), (-2,1), (-2,-1), (1,2), (1,-2), (-1,2), (-1,-2)]
        
        # 检查每一步移动是否有效
        for i in range(n * n - 1):
            x1, y1 = positions[i]
            x2, y2 = positions[i + 1]
            
            valid_move = False
            for dx, dy in moves:
                if x1 + dx == x2 and y1 + dy == y2:
                    valid_move = True
                    break
            
            if not valid_move:
                return False
        
        return True

public class Solution {
    public bool CheckValidGrid(int[][] grid) {
        int n = grid.Length;
        var positions = new (int, int)[n * n];
        
        // 建立从步数到位置的映射
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                positions[grid[i][j]] = (i, j);
            }
        }
        
        // 检查起始位置是否为(0,0)
        if (positions[0] != (0, 0)) {
            return false;
        }
        
        // 骑士的8个可能移动方向
        var moves = new (int, int)[] {(2,1), (2,-1), (-2,1), (-2,-1), (1,2), (1,-2), (-1,2), (-1,-2)};
        
        // 检查每一步移动是否有效
        for (int i = 0; i < n * n - 1; i++) {
            var (x1, y1) = positions[i];
            var (x2, y2) = positions[i + 1];
            
            bool validMove = false;
            foreach (var (dx, dy) in moves) {
                if (x1 + dx == x2 && y1 + dy == y2) {
                    validMove = true;
                    break;
                }
            }
            
            if (!validMove) {
                return false;
            }
        }
        
        return true;
    }
}

var checkValidGrid = function(grid) {
    const n = grid.length;
    
    // Knight must start at (0, 0)
    if (grid[0][0] !== 0) return false;
    
    // Create position array where index is move number, value is [row, col]
    const positions = new Array(n * n);
    
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            positions[grid[i][j]] = [i, j];
        }
    }
    
    // Check if each consecutive move is a valid knight move
    for (let i = 0; i < n * n - 1; i++) {
        const [r1, c1] = positions[i];
        const [r2, c2] = positions[i + 1];
        
        const dr = Math.abs(r2 - r1);
        const dc = Math.abs(c2 - c1);
        
        // Valid knight move: (2,1) or (1,2)
        if (!((dr === 2 && dc === 1) || (dr === 1 && dc === 2))) {
            return false;
        }
    }
    
    return true;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n²)需要遍历网格建立位置映射，然后验证n²-1次移动，每次移动检查8个方向
空间复杂度O(n²)存储位置映射数组需要O(n²)空间

相关题目