C.十面埋伏(DFS&连通块）

题目传送门

题意：将”#“图案用星号围一圈并输出图。

思路：显然从外围DFS，判断一下四周有无#即可。

AC代码：

#include<bits/stdc++.h>
using namespace std;
int n,m;
char mp[505][505];
int vis[505][505],d[4][2]={0,1,0,-1,1,0,-1,0};
void dfs(int x,int y){
	//printf("x=%d,y=%d\n",x,y);
	if(x<1||x>n||y<1||y>m) return;
	if(vis[x][y]||mp[x][y]=='#') return;
	vis[x][y]=1;
	for(int i=0;i<4;i++){
		int nx=x+d[i][0],ny=y+d[i][1];
		if(mp[nx][ny]=='#') mp[x][y]='*';
	}
	dfs(x+1,y),dfs(x-1,y),dfs(x,y+1),dfs(x,y-1);
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%s",mp[i]+1);
	dfs(1,1);
	for(int i=1;i<=n;i++)
		printf("%s\n",mp[i]+1);
	return 0;
}