AcWing 3190. 路径之谜
原题链接
简单
作者:
fun
,
2021-03-18 18:26:08
,
所有人可见
,
阅读 1275
#include <vector>
#include <iostream>
using namespace std;
typedef pair<int,int> PII;
const int N = 30;
int row[N],col[N];
int n;
vector<PII> path;
int dx[]={-1,0,1,0},dy[]={0,1,0,-1};
bool st[N][N];
bool check()
{
for(int i=0;i<n;i++)
if(row[i] || col[i]) return false;
return true;
}
void dfs(int x,int y)
{
row[x]--,col[y]--;
st[x][y]=true;
path.push_back({x,y});
if(row[x]<0 || col[y]<0) return ;
if(x==n-1 && y==n-1 && check())
{
for(int i=0;i<path.size();i++)
cout<<n*path[i].first+path[i].second<<' ';
exit(0);
return ;
}
for(int i=0;i<4;i++)
{
int a=x+dx[i],b=y+dy[i];
if(a<0 ||a>=n ||b<0 ||b>=n) continue;
if(st[a][b]) continue;
dfs(a,b);
path.pop_back();
row[a]++,col[b]++;
st[a][b]=false;
}
}
int main()
{
cin >> n;
for(int i=0;i<n;i++) cin >> col[i];
for(int i=0;i<n;i++) cin >> row[i];
dfs(0,0);
return 0;
}
超时了朋友
这道题目前在acwing上过不掉
兄弟你没有填邀请码可以填一个,都可以得AC币!嘿嘿,谢谢兄弟
我的邀请码是:GUDFH