BFS标记（BFS染色）

链接：https://ac.nowcoder.com/acm/contest/5158/C
来源：牛客网

经过多年的征战，牛牛在与牛可乐的对决渐渐处于下风，于是牛牛决定对牛可乐来一次大围剿。

战场可以看作一张 n∗m 的地图，牛可乐的士兵只能上下左右移动，不能斜着移动，牛牛决定挖一圈陷阱包围牛可乐的士兵。牛牛想知道包围牛可乐的士兵所需要的最少的陷阱数量是多少(划掉，具体请看update)，但是牛牛并不会排兵布阵，于是只能求助于你了。

保证地图的边界处不会有士兵.

保证牛可乐的士兵是连通的

要求牛可乐使用的陷阱构成的包围圈与牛可乐的士兵之间要求是紧密接触的

输入描述:

第一行输入两个整数 n和 m，表示地图的大小

下面 n 行每行 m 个字符，.表示空地，# 表示士兵。

保证输出的字符串只包含 .和 #

输出描述:

输出挖完陷阱后的地图，陷阱用 ∗ 来表示.

输入

复制 6 5 ..... .###. .#.#. .###. ..##. .....

6 5
.....
.###.
.#.#.
.###.
..##.
.....

输出

复制 .***. *###* *#.#* *###* .*##* ..**.

.***.
*###*
*#.#*
*###*
.*##*
..**.

示例2

 

备注:

1≤n,m≤500
这个题用到的是BFS染色
BFS跑一边可以他的外围都标记上

#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
int dx[5]={0,0,1,-1};
int dy[5]={1,-1,0,0};
const int maxn=5e3+100;
struct node{
    int x,y;
};
int n,m;
queue<node>q;
int vis[maxn][maxn];
char a[maxn][maxn];
void BFS(int x,int y){
    node now,next;
    now.x=x;
    now.y=y;
    q.push(now);
    vis[x][y]=1;
    while(!q.empty()){
        now=q.front();
        q.pop();
        for(int i=0;i<=3;i++){
            int xx=now.x+dx[i];
            int yy=now.y+dy[i];
            if(a[xx][yy]=='.'&&xx>=1&&xx<=n&&yy>=1&&yy<=m&&vis[xx][yy]==0){
                vis[xx][yy]=1;
                next.x=xx;
                next.y=yy;
                q.push(next);
            }
        }
    } 
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%s",a[i]+1);
    }
    BFS(1,1);//BFS染色
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(a[i][j]=='#'){
                if(a[i][j-1]=='.'){
                    a[i][j-1]='*'; 
                } 
                if(a[i][j+1]=='.'){
                    a[i][j+1]='*';
                }
                if(a[i+1][j]=='.'){
                    a[i+1][j]='*';
                }
                if(a[i-1][j]=='.'){
                    a[i-1][j]='*';
                }
            }
        }
    }
    for(int i=1;i<=n;i++){//主要是其内部的.变成了*，要变回来
        for(int j=1;j<=m;j++){
            if(a[i][j]=='*'&&vis[i][j]==0){
                a[i][j]='.';
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            printf("%c",a[i][j]);
        }
        printf("
");
    }
}