小明冒充X星球的骑士，进入了一个奇怪的城堡。
城堡里边什么都没有，只有方形石头铺成的地面。
假设城堡地面是 n x n 个方格。如下图所示：
按习俗，骑士要从西北角走到东南角。
可以横向或纵向移动，但不能斜着走，也不能跳跃。
每走到一个新方格，就要向正北方和正西方各射一箭。
（城堡的西墙和北墙内各有 n 个靶子）
同一个方格只允许经过一次。但不必做完所有的方格。
如果只给出靶子上箭的数目，你能推断出骑士的行走路线吗？
有时是可以的，比如图1.png中的例子。
本题的要求就是已知箭靶数字，求骑士的行走路径（测试数据保证路径唯一）
输入格式
第一行一个整数N(0<N<20)，表示地面有 N x N 个方格
第二行N个整数，空格分开，表示北边的箭靶上的数字（自西向东）
第三行N个整数，空格分开，表示西边的箭靶上的数字（自北向南）
输出格式
一行若干个整数，表示骑士路径。
为了方便表示，我们约定每个小格子用一个数字代表，从西北角开始编号: 0,1,2,3….
比如，图1.png中的方块编号为：
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
本题思路
这道题目，整体就是一个很经典的dfs，一个迷宫类型题的变形，从原点出发一旦走过就对对应的方向射箭数减一，然后递归寻找答案，最后记录在数组输出即可，值得注意的是，要记得返回，还有对于明显出错的方向控制
本人在解答时主要遇到的问题是，忘记对0，0出发点的数据进行标记，导致出错，dfs这种忘记初始化的情况很多，加上蓝桥不能检验的提交方式，还是要注意的
这题常规的迷宫变形，难度不大，主要不要忘记初始数据的扣除标记！！！
下面上代码
import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
public class Main路径之谜 {
static int aa[],bb[];
static int lj[],n,k=1;
static int fx[][]= {{1,0},{0,1},{-1,0},{0,-1}};
static boolean jl[][],f=false;
public static void main(String[] args) throws IOException {
StreamTokenizer x=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
PrintWriter out=new PrintWriter(System.out);
x.nextToken();
n=(int)x.nval;
aa=new int[n];
bb=new int[n];
for(int i=0;i<n;i++) {
x.nextToken();
bb[i]=(int)x.nval;
}
for(int i=0;i<n;i++) {
x.nextToken();
aa[i]=(int)x.nval;
}
lj=new int[405];
jl=new boolean[n][n];
aa[0]--;//标记0，0
bb[0]--;//标记0，0
jl[0][0]=true;//标记0，0
dfs(new Point(0, 0));
lj[0]=0;
for(int i=0;i<k;i++) {
if(i!=k-1)
out.print(lj[i]+" ");
else
out.println(lj[i]);
}
out.flush();
}
public static void dfs(Point p) {
if(p.x==n-1&&p.y==n-1&&cc()) {
f=true;
return;
}
for(int i=0;i<4;i++) {
int x=p.x+fx[i][0];
int y=p.y+fx[i][1];
if(x>=0&&x<n&&y>=0&&y<n&&!jl[x][y]) {
if(aa[x]-1<0||bb[y]-1<0)//发现不符合限制返回
continue;
aa[x]--;
bb[y]--;
jl[x][y]=true;
lj[k++]=x*n+y;
dfs(new Point(x,y));
if(f)//找到答案直接返回
return;
k--;
aa[x]++;
bb[y]++;
jl[x][y]=false;
}
}
}
public static boolean cc() {//检查是否满足规范
for(int i=0;i<n;i++) {
if(aa[i]!=0||bb[i]!=0)
return false;
}
return true;
}
}