Question

将waim围绕'#'的'.'换成'*'。

Solution

DFS将圈外的'.'格子标记,然后将'#'的周围有被标记过的格子改为'*'。

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  maxn = 1e6 + 5;
const int N = 500 + 5;

int n,m;
char s[N][N];
bool v[N][N];
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};

void dfs(int x,int y){
    v[x][y]=true;
    for(int i=0;i<4;i++){
        int tx=x+dx[i];
        int ty=y+dy[i];
        if(v[tx][ty]||tx<1||tx>n||ty<1||ty>m||s[tx][ty]!='.') continue;
        dfs(tx,ty);
    }
}

void check(int x,int y){
    if(v[x][y]) s[x][y]='*';
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>s[i]+1;
    }
    dfs(1,1);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(s[i][j]=='#'){
                for(int k=0;k<4;k++){
                    int tx=i+dx[k];
                    int ty=j+dy[k];
                    check(tx,ty);
                }
            }
        }
    }
    for(int i=1;i<=n;i++){
        cout<<s[i]+1<<'\n';
    }
    return 0;
}