题目链接：https://www.lanqiao.cn/problems/89/learning/
    题目描述：
    image.png
    数据规模：
    image.png

    题目思路：数据规模较小，可以用深搜暴力求解，其实这个就是 dfs 迷宫问题的变形，我们从迷宫的入口（左上角）开始搜索，直到走到迷宫的出口（右上角）停止。不过在这里会多了几个约束，比如每次走到一个新格子，需要向 北面的墙 和 西面的墙 射箭，只有当走到迷宫时，在两面的墙射箭的数量等于题目给定的值，才算解决了这个问题。还有一个问题就是在这一过程我们要不断维护一个路径（从入口到出口）。

    写代码遇到的几个细节：

    1. 在搜索到匹配的值时，直接就输出答案，不然在dfs退栈时会把完整的答案破坏，除非在回溯时加上判断标志。
    2. 记得剪枝操作，如果在某一面的墙的箭 > 大于题目给定的数值，那么就没必要搜索下去，因为接着搜索下去只会让值更大。
    3. 在遇到迷宫出口时，不需要对其做额外的回溯处理，因为这个已经包含在了dfs的主体中了。
    1. import java.util.ArrayList;
    2. import java.util.List;
    3. import java.util.Scanner;
    4. // 1:无需package
    5. // 2: 类名必须Main, 不可修改
    7. public class Main {
    8.     static int n;
    9.     static int[][] map;
    10.     static int[] north1, west1;
    11.     static int[] north2, west2;
    12.     static boolean[][] visited;
    13.     static int[][] dirs = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
    14.     static List<Integer> ans = new ArrayList<>();
    15.     static boolean is_end = false;
    16.     static boolean judge(){
    17.         for(int i = 0; i < n; i++){
    18.             if(west1[i] != west2[i]){
    19.                 return false;
    20.             }
    21.             if(north1[i] != north2[i]){
    22.                 return false;
    23.             }
    24.         }
    25.         return true;
    26.     }
    27.     static void dfs(int row, int col){
    28.         if(row == n-1 && col == n-1){
    29.             if(judge()){
    30.                 for(int i = 0; i < ans.size(); i++){
    31.                     if(i != ans.size()-1)
    32.                         System.out.printf(ans.get(i) + " ");
    33.                     else
    34.                         System.out.printf(ans.get(i) + "\n");
    35.                 }
    36.                 is_end = true;
    37.             }
    38.             return;
    39.         }
    40.         if(is_end){
    41.             return;
    42.         }
    43.         if(west2[row] > west1[row] || north2[col] > north1[col]){
    44.           return;
    45.         }
    46.         //向四个方向进行搜索
    47.         for(int i = 0; i < 4; i++){
    48.             int newRow = row + dirs[i][0];
    49.             int newCol = col + dirs[i][1];
    50.             if(newRow < 0 || newRow >= n || newCol < 0 || newCol >= n){
    51.                 continue;
    52.             }
    53.             if(!visited[newRow][newCol]){
    54.                 visited[newRow][newCol] = true;
    55.                 ans.add(map[newRow][newCol]);
    56.                 north2[newCol]++;
    57.                 west2[newRow]++;
    58.                 dfs(newRow, newCol);
    59.                 visited[newRow][newCol] = false;
    60.                 ans.remove(Integer.valueOf(map[newRow][newCol]));
    61.                 north2[newCol]--;
    62.                 west2[newRow]--;
    63.             }
    64.         }
    65.     }
    66.     public static void main(String[] args) {
    67.         Scanner scan = new Scanner(System.in);
    68.         n = scan.nextInt();
    70.         north1 = new int[n];
    71.         west1 = new int[n];
    72.         north2 = new int[n];
    73.         west2 = new int[n];
    74.         for(int i = 0; i < n; i++){
    75.             north1[i] = scan.nextInt();
    76.         }
    77.         for (int i = 0; i < n; i++){
    78.             west1[i] = scan.nextInt();
    79.         }
    81.         map = new int[n][n];
    82.         visited = new boolean[n][n];
    83.         int num = 0;
    84.         for(int i = 0; i < n; i++){
    85.             for(int j = 0; j < n; j++){
    86.                 map[i][j] = num++;
    87.             }
    88.         }
    90.         //深搜前的初始化
    91.         visited[0][0] = true;
    92.         ans.add(0);
    93.         west2[0]++;
    94.         north2[0]++;
    95.         dfs(0, 0);
    96.         //0 4 5 1 2 3 7 11 10 9 13 14 15
    98.     }
    99. }