文章

17

粉丝

166

获赞

6

访问

136.2k

头像
BFS 注意边界
P1126
发布于2021年2月24日 12:27
阅读数 7.5k

#include <bits/stdc++.h>

using namespace std;

const int N = 35;
typedef pair<int, int> PII;
int n, m, times;
char g[N][N]; //存储地图
int d[N][N];  //存储距离 -1表示还未遍历
int dx[] = {0, -1, 0, 1}, dy[] = {1, 0, -1, 0};

void bfs(int sx, int sy)
{
    queue<PII> q;
    q.push({sx, sy});
    g[sx][sy] = '#', d[sx][sy] = 0;
    
    while(q.size())
    {
        auto t = q.front();
        q.pop();
        
        if(d[t.first][t.second] == times)
        {
            for(int i = 0; i < n; i++) puts(g[i]);
            puts("");
            return;
        }
        
        for(int i = 0; i < 4; i++)
        {
            int x = t.first + dx[i], y = t.second + dy[i];
            if(g[x][y] == '.' && d[x][y] == -1)
            {
                d[x][y] = d[t.first][t.second] + 1, g[x][y] = '#';
                q.push({x, y});
            }
        }
    }
    cout << "No" << endl; //如果前面没有return说明早已充满
    re...
登录查看完整内容


登录后发布评论

暂无评论,来抢沙发