题目1834:蓝桥杯2016年第七届真题-路径之谜

#include<iostream>
using namespace std;
int n;
int a[20],b[20];//a自西向东的靶数，b自北向南的靶数
int arr[20][20];//格子
int vis[20][20];//标记是否访问过
int top;//栈顶
int stack[20];//存储路线的栈
int dx[4]={1,0,-1,0};//下左上右
int dy[4]={0,-1,0,1};//下左上右

bool check(){//检查靶子
for(int i=0;i<n;i++){
if(a[i]!=0||b[i]!=0){
return false;
}
}
return true;
}

void dfs(int x,int y,int step){
if(a[y]<0||b[x]<0){
return;
}
if(x==n-1&&y==n-1){//终止条件，到达最后一个格子
if(check()){
for(int i=0;i<top;i++){
cout<<stack[i]<<" ";
}
cout<<endl;
}
return;
}
for(int i=0;i<4;i++){
int tx,ty;
tx=x+dx[i];
ty=y+dy[i];
if(tx>=0&&tx<n&&ty>=0&&ty<n&&vis[tx][ty]==0){
vis[tx][ty]=1;
stack[top++]=arr[tx][ty];
a[ty]--;
b[tx]--;
dfs(tx,ty,step+1);
a[ty]++;
b[tx]++;
top--;//出栈
vis[tx][ty]=0;
}
}
}

int main(){
cin>>n;
for(int i=0;i<n;i++){
cin>>a[i];
}
for(int i=0;i<n;i++){
cin>>b[i];
}
for(int i=0,k=0;i<n;i++){
for(int j=0;j<n;j++){
arr[i][j]=k++;//为每个格子分配编号
}
}
vis[0][0]=1;
stack[0]=arr[0][0];
top=1;
a[0]--;
b[0]--;
dfs(0,0,1);
return 0;
}