检查骑士巡视方案

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.

/*
 * 思路：
 * 使用Java Stream API简化代码。主要思路保持一致，利用stream遍历棋盘并验证每一步移动的合法性。
 */
import java.util.stream.IntStream;

public class KnightTourStream {
    public boolean checkValidGrid(int[][] grid) {
        int n = grid.length;
        int[] position = new int[n * n];
        IntStream.range(0, n).forEach(i -> IntStream.range(0, n).forEach(j -> position[grid[i][j]] = i * n + j));
        int[] dx = {-2, -1, 1, 2, 2, 1, -1, -2};
        int[] dy = {1, 2, 2, 1, -1, -2, -2, -1};
        return IntStream.range(1, n * n).allMatch(k -> {
            int prev = position[k - 1];
            int curr = position[k];
            int prevX = prev / n;
            int prevY = prev % n;
            int currX = curr / n;
            int currY = curr % n;
            return IntStream.range(0, 8).anyMatch(d -> currX == prevX + dx[d] && currY == prevY + dy[d]);
        });
    }
}

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

O(n^2 log n)

O(n^2)