CodeForces 525D Arthur and Walls

广搜。看了官方题解才会的.....

定义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 ;

}