2596. 检查骑士巡视方案

题目描述

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

解法一：DFS

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


func checkValidGrid(grid [][]int) bool {
    h, w := len(grid), len(grid[0])
    dirs := [][2]int{{1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}, {-2, -1}, {-2, 1}, {-1, 2}}
    var dfs func(x, y, id int) bool
    dfs = func(x, y, id int) bool {
        if grid[x][y] != id {
            return false
        }
        if grid[x][y] == h*w-1 {
            return true
        }
        for _, dir := range dirs {
            nx, ny := x+dir[0], y+dir[1]
            if 0 <= nx && nx < w && 0 <= ny && ny < h {
                if dfs(nx, ny, id+1) {
                    return true
                }
            }
        }
        return false
    }
    return dfs(0, 0, 0)
}

解法二：直接模拟

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28


func checkValidGrid(grid [][]int) bool {
    if grid[0][0] != 0 {
        return false;
    }
    n := len(grid)
    indices := make([][2]int, n * n)
    for i := 0; i < n; i++ {
        for j := 0; j < n; j++ {
            indices[grid[i][j]][0] = i;
            indices[grid[i][j]][1] = j;
        }
    }
    for i := 1; i < n * n; i++ {
        dx := abs(indices[i][0] - indices[i - 1][0])
        dy := abs(indices[i][1] - indices[i - 1][1])
        if dx * dy != 2 {
            return false
        }
    }
    return true
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}