路径之迷
C++代码
#include<bits/stdc++.h>
using namespace std;
const int N = 20;
bool vis[N][N];
int row[N],col[N];
int g[N][N];
int n;
int dx[] = {-1,0,1,0},dy[] = {0,1,0,-1};
vector<int> res;
bool f;
bool check()
{
for(int i = 0;i<n-1;i++)
{
if(row[i] > 0 || col[i] >0)
return false;
}
return true;
}
void dfs(int x,int y)
{
if(!row[y] || !col[x])
{
return ;
}
if(x<0 || x>=n || y<0 || y>=n || vis[x][y] || f)
{
return ;
}
if(x == n-1 && y == n-1)
{
for(int i = 0;i<n-1;i++)
{
if(row[i] > 0 || col[i] >0)
return ;
}
f = true;
res.push_back(g[x][y]);
for(int i = 0;i<res.size();i++)
cout<<res[i]<<' ';
res.pop_back();
}
for(int i = 0;i<4;i++)
{
int xx = x +dx[i],yy = y +dy[i];
if(!vis[x][y])
{
vis[x][y] = true;
row[y]--;
col[x]--;
res.push_back(g[x][y]);
dfs(xx,yy);
vis[x][y] = false;
row[y]++;
col[x]++;
res.pop_back();
}
}
}
int main()
{
cin>>n;
int r = 0;
for(int i = 0;i<n;i++)
{
for(int j = 0;j<n;j++)
{
g[i][j] = r;
r++;
}
}
for(int i = 0;i<n;i++)
cin>>row[i];
for(int i = 0;i<n;i++)
cin>>col[i];
dfs(0,0);
}