@toc

1、题目描述

小明冒充 X 星球的骑士，进入了一个奇怪的城堡。

城堡里边什么都没有，只有方形石头铺成的地面。

假设城堡地面是 n×n* 个方格。如下图所示。

按习俗，骑士要从西北角走到东南角。可以横向或纵向移动，但不能斜着走，也不能跳跃。每走到一个新方格，就要向正北方和正西方各射一箭。（城堡的西墙和北墙内各有 n 个靶子）同一个方格只允许经过一次。但不必走完所有的方格。如果只给出靶子上箭的数目，你能推断出骑士的行走路线吗？有时是可以的，比如上图中的例子。

本题的要求就是已知箭靶数字，求骑士的行走路径（测试数据保证路径唯一）

输入描述

第一行一个整数 N* (0≤N≤20)，表示地面有 N×N* 个方格。

第二行 N 个整数，空格分开，表示北边的箭靶上的数字（自西向东）

第三行 N 个整数，空格分开，表示西边的箭靶上的数字（自北向南）

输出描述

输出一行若干个整数，表示骑士路径。

为了方便表示，我们约定每个小格子用一个数字代表，从西北角开始编号: 0,1,2,3 ⋯⋯

比如，上图中的方块编号为：

0 1 2 3

4 5 6 7

8 9 10 11

12 13 14 15

输入输出样例

示例

输入

4
2 4 3 4
4 3 3 3

输出

0 4 5 1 2 3 7 11 10 9 13 14 15

运行限制

• 最大运行时间：5s
• 最大运行内存: 256M

2、解题思路

看到这种给一个起点和终点走方格的时候，第一反应就应该是DFS或者BFS了，一条路走到黑这种适合DFS，这题很符合。

骑士从左上角起点出发，没走一步，往左边和上边对应位置射一箭，题目在方格的左边和上边给出了骑士从起点到终点射箭的数量，现在让我们求骑士行走的路线。

那我们可以逆向一下，我们从入口开始走，没走一步就将当前位置左边和上边箭的数量减一，如果我们走到了终点且当前所有箭靶上箭的数量为零，则说明我们所走的路线就是骑士经过的路线。

我们设置一个方向

 public static int[][] dirs = {
            {-1, 0},    //上
            {1, 0},     //下
            {0, -1},    //左
            {0,1}       //右
    };

从起点开始DFS，没走一个新的位置，就要进行判断

• 如果该点是终点，且箭靶上箭的数量为0，则说明走过的路线就是骑士经过的路线，算法结束。
• 如果当前点不是终点，且没有被访问过，那么我们可以用一个path数组记录下该路径，然后继续向上下左右进行DFS。
• 如果走到终点且箭靶上的箭还没有被拔完，那我们就要济宁回溯操作(标记当前点未访问，左边箭靶数量+1，上边箭靶数量+1)。

3、代码实现

package 国赛打游击.路径之谜;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;

public class Main {
    public static StreamTokenizer st=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    public static int[] path;   //记录走位置对应的编号
    public static int n;    //n*n的矩阵
    public static int[] countLeft;//左边箭靶上的箭
    public static int[] countUp;//上边箭靶上的箭
    public static boolean[][] visited;  //访问标记
    public static boolean success=false; //走到终点的标记
    public static int[][] dirs = {
            {-1, 0},    //上
            {1, 0},     //下
            {0, -1},    //左
            {0,1}       //右
    };

    public static void main(String[] args) throws IOException{
        n=nextInt();  //n*n的矩阵
        countLeft=new int[n];
        countUp=new int[n];
        path=new int[n*n];
        visited=new boolean[n][n];
        for (int i = 0; i <n ; i++) {
            countLeft[i]=nextInt();
        }
        for (int i = 0; i <n ; i++) {
            countUp[i]=nextInt();
        }
        //从起点开始dfs
        dfs(0,0,0);
    }

    public static void dfs(int x,int y,int step){
        path[step]=y*n+x;   //将该点编号记录到路径中
        visited[x][y]=true; //访问标记
        countLeft[x]--; //拔掉当前行左边的箭
        countUp[y]--;   //拔掉当前列上边的箭
        if(x==n-1&&y==n-1&&check()){    //是否到达终点
            success=true;   //标记已经走到终点
            //输出答案
            for (int i = 0; i <=step ; i++) {
                System.out.print(path[i]+" ");
            }
            return;
        }
        for (int[] dir : dirs) {    //四个方向搜索
            int tmpX=x+dir[0];
            int tmpY=y+dir[1];
            //没有到达终点且不越界，且(tmpX,tmpY)没有被访问过
            if(!success&&tmpX>=0&&tmpX<=n-1&&tmpY>=0&&tmpY<=n-1&&!visited[tmpX][tmpY]){
                if(countLeft[tmpX]>0&&countUp[tmpY]>0){//左边和上边还有箭
                    dfs(tmpX,tmpY,step+1);//搜索下一步
                    visited[tmpX][tmpY]=false;  //复原，回溯
                    countLeft[tmpX]++;
                    countUp[tmpY]++;
                }
            }
        }
    }
    public static boolean check(){
        for (int i = 0; i < n; i++) {
            //到终点的时候箭还没有拔完
            if(countLeft[i]!=0||countUp[i]!=0){
                return false;
            }
        }
        //到终点时箭刚好拔完
        return true;
    }

    public static int nextInt() throws IOException{
        st.nextToken();
        return (int)st.nval;
    }
}

跑一个测试用例看看

我们 $path[]$数组中记录的是经过的每个方格的编号，最后将这些编号输出即为骑士从起点到终点走过的路径。