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; }