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
2.题解：
本题实质上是个DFS问题，根据给定的已知条件：北边和西边箭靶上箭的个数，逆推出路径。可以正向dfs，即设定两个空数组，每走过一个格子北面和西面的箭靶各加1。但在这道题更适合的方法是认为是一道拔箭问题，即每走过一个格子北面和西面的箭靶各减1，条件判断为：不能越界，不能走已经走过的格子，不能走已经满足箭靶上箭个数的格子。接下来设定check函数，用于判断是否走到了终点且满足每个箭靶的数量全部为0（全部拔光了）不满足则返回false，若满足条件，将保存的路径坐标转化为题目要求的输出格式，并返回false（原路恢复原样返回），若未到达终点，返回true。在主体的dfs函数中，首先用check函数检查是否到达了终点（false则return，回到上一层进行回溯，true则跳到else语句）else语句中首先对现有坐标进行上下左右的移动，按循环顺序选择符合条件判断的一个方向移动，接着进行拔箭，保存路径和标记已走过。然后进行递归dfs()进入下一层，在这之后设定回溯初始化，和递归的操作相反，放箭，删除路径和标记未走过，这里的代码是在dfs()执行完之后再去执行的，dfs()执行完说明最下层上下左右尝试过都不行一直return回溯到这一层。main函数里接受输入的数据。对于起点，由于进入dfs的点默认都是经过拔箭，保存路径和标记已走过处理的，因此要在main中提前处理。
3.详细c++代码
include
using namespace std;
struct ball//结果路径坐标容器
{
int first;//横坐标
int second; //纵坐标
};
int n;//行列数
const int N=30;
int row[N];//记录北边靶子的箭数
int col[N];//记录西边靶子的箭数
bool flag[N][N];
//上下左右的方向
int ax[4]={0,1,-1,0};
int ay[4]={1,0,0,-1};
//用来保存路径 ，xy对
vector res;
bool pd(int dx,int dy)//判断是否符合条件（不能越界，不能走已经走过的格子，不能走已经满足箭靶上箭个数的格子）
{
if(flag[dx][dy]==1)
return false;
if(dx<0) return false; if(dx>n-1)
return false;
if(dy<0) return false; if(dy>n-1)
return false;
if(row[dy]<=0)
return false;
if(col[dx]<=0)
return false;
return true;
}
bool check(int dx,int dy)//仅当走到终点时使用：检查箭是否全部拔光，若全部拔光输出结果。不管怎么样全部return false（用来回溯）
{
if(dx==(n-1)&&dy==(n-1))
{
for(int i=0;i<n;i++)
{
if(row[i]!=0)
return false; //北面的箭全部拔光
}
for(int i=0;i<n;i++)
{
if(col[i]!=0)//西面的箭全部拔光
return false;
}
for(int i=0;i<res.size();i++)//按照输出格式输出结果
{
int hx=res[i].first;
int hy=res[i].second;
int sum=n*hx+hy;
cout<<sum<<" ";
}
return false;
}
return true;
}
void dfs(int dx,int dy)
{
if(check(dx,dy)==false)//检查走到终点时路径是否正确
{
return;//回溯返回
}
else
{
for(int i=0;i<4;i++)
{
int x=dx+ax[i];
int y=dy+ay[i];
if(pd(x,y)==false) //检查是否符合条件
{
continue;
}
else
{
flag[x][y]=1;
row[y]--;col[x]--;
res.push_back({x,y});//拔箭，保存路径和标记已走过
dfs(x,y);//递归
res.pop_back();
row[y]++;col[x]++;
flag[x][y]=0;//回溯返回后恢复原状
}
}
}
}
int main()
{
//接受数据
cin>>n;
for(int i=0;i>row[i];
}
for(int i=0;i>col[i];
}
//对于起点，由于进入dfs的点默认都是经过拔箭，保存路径和标记已走过处理的，因此要在main中提前处理
flag[0][0]=1;
col[0]--;
row[0]--;
res.push_back({0,0});
dfs(0,0);
return 0;
}
感谢大家的观看！！！别忘记点赞哦！！！
