这题明显可以用多源bfs来做啊
查看原帖
这题明显可以用多源bfs来做啊
1057414
kaduoyazikasa楼主2024/5/9 16:16
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#define x first
#define y second

using namespace std;
typedef pair<int, int> PII;
const int N = 110;
queue<PII> q;
char g[N][N];
int dist[N][N];
int n,m;
int dx[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
int dy[8] = {-1, 0, 1, 1, 1, 0, -1, -1};

void bfs(){
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(g[i][j]=='*')
                q.push({i,j});
    
    while(q.size()){
        auto t  = q.front();q.pop();
        for(int i=0;i<8;i++){
            int a = t.x+dx[i],b=t.y+dy[i];
            if(a<1||a>n||b<1||b>m)continue;
            if(g[a][b]=='*')continue;
            if(g[a][b]==0) dist[a][b] = dist[t.x][t.y]+1;
            else dist[a][b]++;
            
        }
    }    

}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>g[i]+1;
    }
    
    bfs();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(g[i][j]=='*')cout<<'*';
            else cout<<dist[i][j];
        }cout<<endl;
    }
    
}
2024/5/9 16:16
加载中...