广搜。看了官方题解才会的.....
定义2*2的小矩阵,有三个是点,一个是星,这样的小矩阵被称为元素块。
首先把所有元素块压入队列,每次取出对头,检查是否还是元素块,如果是 那么将那个*改为点,否则跳过
改完之后,检查周围8个点是否是元素块,如果有新产生的元素块,那么压入队列。
这样操作完之后就是答案。
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std; struct Node
{
int a,b;
Node(int A,int B){a=A,b=B;}
};
queue<Node>Q;
const int N=;
int n, m;
char g[N][N]; bool check(int x, int y)
{
if (g[x][y] == '.' || x < || y < || x >= n || y >= m)return ;
if (g[x][y - ] == '.'&&g[x - ][y - ] == '.'&&g[x - ][y] == '.')return ;
if (g[x - ][y] == '.'&&g[x - ][y + ] == '.'&&g[x][y + ] == '.')return ;
if (g[x][y + ] == '.'&&g[x + ][y + ] == '.'&&g[x + ][y] == '.')return ;
if (g[x][y - ] == '.'&&g[x + ][y - ] == '.'&&g[x + ][y] == '.')return ;
return ;
} void bfs()
{
for(int i=;i<n;i++)
for(int j=;j<m;j++) if(check(i,j)) Q.push(Node(i,j)); while(!Q.empty())
{
Node h=Q.front(); Q.pop();
if(!check(h.a,h.b)) continue;
g[h.a][h.b]='.'; for(int i=-;i<=;i++)
{
for(int j=-;j<=;j++)
{
if(i==&&j==) continue;
if(check(h.a+i,h.b+j)) Q.push(Node(h.a+i,h.b+j));
}
}
}
} int main()
{
while (~scanf("%d%d", &n, &m))
{
for (int i = ; i < n; i++) scanf("%s", g[i]);
bfs();
for(int i=;i<n;i++) printf("%s\n",g[i]);
}
return ;
}