bfs60分求助
  • 板块P3395 路障
  • 楼主Channel_Choo
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/8/25 10:08
  • 上次更新2023/11/3 01:22:07
查看原帖
bfs60分求助
787888
Channel_Choo楼主2023/8/25 10:08
#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 - 1].first][point[now.step - 1].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;
}

#4#5WA

2023/8/25 10:08
加载中...