社区讨论

求助

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 条回复,欢迎继续交流。

正在加载回复...