（2596. 检查骑士巡视方案leetcode,经典深搜）-------------------Java实现

（2596. 检查骑士巡视方案leetcode,经典深搜）-------------------Java实现

题目表述

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

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

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

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

样例

条件

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

思路

注意点

ac代码

Java:

package leetcode2596;

import java.util.Scanner;

class Solution {
    public boolean checkValidGrid(int[][] grid) {
        int now = 0;
        int now_x = 0,now_y = 0;
        int n = grid.length;
        boolean flag =false;
        int[][] next_step = new int[][]{{2,1},{2,-1},{-2,1},{-2,-1},
                                        {1,2},{1,-2},{-1,2},{-1,-2}
        };
        if(grid[0][0]!=0)
            return false;
        while(now<n*n){
            for (int i=0;i<8;i++)
            {
                now_x+=next_step[i][0];
                now_y+=next_step[i][1];
                if (now_x>=0&&now_x<n&&now_y>=0&&now_y<n&&grid[now_x][now_y]==(now+1))
                {now++;flag=true;break;}
                now_x-=next_step[i][0];
                now_y-=next_step[i][1];
            }
            if (flag)
                flag=false;
            else
                break;
        }
        System.out.println("now:"+now);
        return now==(n*n-1)?true:false;
    }
}
public class leetcode2596 {
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int n = cin.nextInt();
        cin.nextLine();
        int [][] grid = new int[n][];
        for (int i=0;i<n;i++)
        {
            grid[i] = new int[n];
            for (int j=0;j<n;j++)
                grid[i][j] = cin.nextInt();
            cin.nextLine();
        }

        for (int[] x :grid)
        {
         for (int y:x)
             System.out.print(y+" ");
            System.out.println();
        }
            Solution s = new Solution();
        System.out.println(s.checkValidGrid(grid));
    }
}
//input
//5
//0 11 16 5 20
//17 4 19 10 15
//12 1 8 21 6
//3 18 23 14 9

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/squares-of-a-sorted-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。