路径之谜
小明冒充X星球的骑士，进入了一个奇怪的城堡。 城堡里边什么都没有，只有方形石头铺成的地面。
假设城堡地面是 n x n 个方格。【如图1.png】所示。
按习俗，骑士要从西北角走到东南角。 可以横向或纵向移动，但不能斜着走，也不能跳跃。 每走到一个新方格，就要向正北方和正西方各射一箭。 （城堡的西墙和北墙内各有 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
资源约定： 峰值内存消耗 < 256M CPU消耗 < 1000ms
请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。
所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。
注意: main函数需要返回0 注意: 只使用ANSI C/ANSI C++ 标准，不要调用依赖于编译环境或操作系统的特殊函数。 注意: 所有依赖的函数必须明确地在源文件中 #include <xxx>， 不能通过工程设置而省略常用头文件。
提交时，注意选择所期望的编译器类型。 解题思路：判断x.y的取值范围最好在dfs之前判断，减少运算量，利用边界条件进行判断
#include<bits/stdc++.h> using namespace std; const int N=20; int north[N+10]; int west[N+10]; int move_x[4]={0,-1,0,1}; int move_y[4]={-1,0,1,0}; int n; int val[N+10][N+10]; int vst[N*N+100]; int flag=0; int path[N+10]; int id=0; void dfs(int x,int y,int k){ if(flag)return; if(north[y]<0||west[x]<0) return; if(x==n-1&&y==n-1&&north[0]==0&&north[1]==0&&north[2]==0&&north[3]==0&&west[0]==0&&west[1]==0&&west[2]==0&&west[3]==0){ id=k; flag=1; return; } for(int i=0;i<4;i++){ int xx=x+move_x[i]; int yy=y+move_y[i]; if(xx<0||xx>=n||yy<0||yy>=n) continue; if(!vst[val[xx][yy]]){ vst[val[xx][yy]]=1; north[yy]--; west[xx]--; k++; path[k]=val[xx][yy]; dfs(xx,yy,k); if(flag) return; vst[val[xx][yy]]=0; north[yy]++; west[xx]++; k--; } } } int main(){ std::ios::sync_with_stdio(false); std::cin.tie(0); cin>>n; for(int i=0;i<n;i++){ cin>>north[i]; } for(int i=0;i<n;i++){ cin>>west[i]; } int k=0; for(int i=0;i<n;i++){//矩阵的初始化 for(int j=0;j<n;j++){ val[i][j]=k; k++; } } memset(vst,0,sizeof(vst)); north[0]--; west[0]--; vst[0]=1; path[0]=0; dfs(0,0,0); for(int i=0;i<=id;i++){ if(i!=0) cout<<" "; cout<<path[i]; } return 0; }
