社区讨论
求助
P3395路障参与者 2已保存回复 1
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 1 条
- 当前快照
- 1 份
- 快照标识符
- @m3s36qg4
- 此快照首次捕获于
- 2024/11/22 09:52 去年
- 此快照最后确认于
- 2025/11/04 14:13 4 个月前
CPP
#include <iostream>
#include <queue>
using namespace std;
int T, n;
pair<int,int> point[1001];
struct point_and_step
{
int x, y, step;
};
char c[1001][1001];
bool vis[1001][1001], f;
int dx[4] = {0, 0, -1, 1};
int dy[4] = {1, -1, 0, 0};
void bfs(int startx, int starty, int step)
{
queue <point_and_step> q;
for (int i = 0;i < 1001;i++)
for (int j = 0;j < 1001;j++)
c[i][j] = '*'/*地图*/, vis[i][j] = false/*是否走过*/;/*初始化*/
for (int i = 1;i <= n;i++)
for (int j = 1;j <= n;j++)
c[i][j] = '.';/*可行走*/
f = false;
q.push((point_and_step){startx, starty, step});
vis[startx][starty] = true;
while (q.size() != 0)
{
point_and_step now = q.front();
q.pop();
if (now.x == n && now.y == n)
{
f = true;
break;
}
c[point[now.step].first][point[now.step].second] = '*';
for (int i = 0;i < 4;i++)
{
int nx = now.x + dx[i];
int ny = now.y + dy[i];
int ns = now.step + 1;
if (nx >= 1 && nx <= n && ny >= 1 && ny <= n && c[nx][ny] == '.' && !vis[nx][ny])
{
q.push((point_and_step){nx, ny, ns});
vis[nx][ny] = true;
}
}
}
if (f)
{
cout << "Yes\n";
}
else
{
cout << "No\n";
}
}
int main()
{
cin >> T;
while (T--)
{
cin >> n;
for (int i = 1;i <= 2 * n - 2;i++)
{
cin >> point[i].first >> point[i].second;
}
bfs(1, 1, 0);
}
return 0;
}
只能A#1~#3,60pts,求助!!!
帮助必关
回复
共 1 条回复,欢迎继续交流。
正在加载回复...