AcWing 3190. 路径之谜
原题链接
简单
作者:
Revui
,
2024-04-12 20:56:24
,
所有人可见
,
阅读 7
#include <bits/stdc++.h>
using namespace std;
const int N = 25;
bool visited[N][N];
int row[N], col[N];
vector<int> path;
int n;
int d[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
void dfs(int x, int y)
{
if (row[x] < 0 || col[y] < 0) return;
if (x == n - 1 && y == n - 1)
{
bool flag = true;
for (int i = 0; i < n; i++)
{
if (row[i] != 0 || col[i] != 0)
{
flag = false;
}
}
if (flag)
{
for (int i = 0; i < path.size(); i++)
{
cout << path[i] << ' ';
}
exit(0);
}
else return;
}
for (int i = 0; i < 4; i++)
{
int nx = x + d[i][0], ny = y + d[i][1];
if (nx < 0 || nx > n - 1 || ny < 0 || ny > n - 1) continue;
if (visited[nx][ny]) continue;
//保存现场
row[nx]--, col[ny]--;
path.push_back(nx * n + ny);
visited[nx][ny] = true;
dfs(nx, ny);
//恢复现场
row[nx]++, col[ny]++;
path.pop_back();
visited[nx][ny] = false;
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
for (int i = 0; i < n; i++) cin >> col[i];
for (int i = 0; i < n; i++) cin >> row[i];
row[0]--, col[0]--;
path.push_back(0);
visited[0][0] = true;
dfs(0, 0);
return 0;
}