526互联

[LeetCode] 2596. Check Knight Tour Configuration

发布时间 2023-09-16 02:17:07作者: CNoodle

There is a knight on an n x n chessboard. In a valid configuration, the knight starts at the top-left cell of the board and visits every cell on the board exactly once.

You are given an n x n integer matrix grid consisting of distinct integers from the range [0, n * n - 1] where grid[row][col] indicates that the cell (row, col) is the grid[row][col]th cell that the knight visited. The moves are 0-indexed.

Return true if grid represents a valid configuration of the knight's movements or false otherwise.

Note that a valid knight move consists of moving two squares vertically and one square horizontally, or two squares horizontally and one square vertically. The figure below illustrates all the possible eight moves of a knight from some cell.

 

Example 1:

Input: 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]]
Output: true
Explanation: The above diagram represents the grid. It can be shown that it is a valid configuration.

Example 2:

Input: grid = [[0,3,6],[5,8,1],[2,7,4]]
Output: false
Explanation: The above diagram represents the grid. The 8th move of the knight is not valid considering its position after the 7th move.

Constraints:

  • n == grid.length == grid[i].length
  • 3 <= n <= 7
  • 0 <= grid[row][col] < n * n
  • All integers in grid are unique.

检查骑士巡视方案。

骑士在一张 n x n 的棋盘上巡视。在 有效 的巡视方案中，骑士会从棋盘的 左上角 出发，并且访问棋盘上的每个格子 恰好一次 。

给你一个 n x n 的整数矩阵 grid ，由范围 [0, n * n - 1] 内的不同整数组成，其中 grid[row][col] 表示单元格 (row, col) 是骑士访问的第 grid[row][col] 个单元格。骑士的行动是从下标 0 开始的。

如果 grid 表示了骑士的有效巡视方案，返回 true；否则返回 false。

注意，骑士行动时可以垂直移动两个格子且水平移动一个格子，或水平移动两个格子且垂直移动一个格子。下图展示了骑士从某个格子出发可能的八种行动路线。

这是一道模拟题。这里我们需要一个额外的二维数组 steps，记录每一步的 [横坐标，纵坐标]。记录好每一步的横纵坐标之后，我们开始遍历每个 index，比如当 index = 1 的时候，我们能从 steps 数组内快速得到棋盘上 1 所在的格子的横纵坐标，我们记为 [x2, y2]。对于骑士上一个位置 index = 0 的横纵坐标，我们也可以很快得到，记为 [x1, y1]。因为骑士只能跳八个点，如果 [x2, y2] 是由 [x1, y1] 能够得到的八个点中的一个而来，就说明 [x2, y2] 是合法的，反之证明从 [x1, y1] 是跳不到 [x2, y2] 的。

时间O(n^2)

空间O(n^2)

Java实现

 1 class Solution {
 2     public boolean checkValidGrid(int[][] grid) {
 3         // corner case
 4         if (grid[0][0] != 0) {
 5             return false;
 6         }
 7 
 8         // normal case
 9         int n = grid.length;
10         int[][] dirs = new int[][] {{-2, -1}, {-2, 1}, {-1, 2}, {-1, -2}, {1, 2}, {1, -2}, {2, 1}, {2, -1}};
11         int[][] step = new int[n * n][2];
12         for (int i = 0; i < n; i++) {
13             for (int j = 0; j < n; j++) {
14                 int id = grid[i][j];
15                 step[id][0] = i;
16                 step[id][1] = j;
17             }
18         }
19 
20         for (int i = 1; i < n * n; i++) {
21             int x1 = step[i - 1][0];
22             int y1 = step[i - 1][1];
23             int x2 = step[i][0];
24             int y2 = step[i][1];
25             boolean state = false;
26             for (int j = 0; j < 8; j++) {
27                 if (x1 + dirs[j][0] == x2 && y1 + dirs[j][1] == y2) {
28                     state = true;
29                 }
30             }
31             if (state == false) {
32                 return false;
33             }
34         }
35         return true;
36     }
37 }

 

LeetCode 题目总结