zzuli 1908

***做的时候判断当前位置为.的上下左右是否为*，如果全是改位置就改为*，如果四周中有为.，再DFS一下，其实就相当于把判断化为更小的子问题***

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<cctype>
#include<queue>
#include<vector>
#include<algorithm>

using namespace std;
typedef long long LL;
#define N 101
#define INF 0x3f3f3f3f

int n, m;
char maps[100][100];
int vis[100][100], w[N][N], b[N][N];
int dir[4][2]= {{1,0}, {0,1}, {-1,0}, {0,-1}};

int DFS(int x, int y)
{
    b[x][y]=1;
    for(int i=0; i<4; i++)
    {
        int nx, ny;
        nx=x+dir[i][0];
        ny=y+dir[i][1];
        if(nx>=0&&nx<n&&ny>=0&&ny<m&&(maps[nx][ny]=='*'||b[nx][ny]))
            w[x][y]++;
        else if(nx>=0&&nx<n&&ny>=0&&ny<m&&(maps[nx][ny]=='.'&&!b[nx][ny]))
        {
            if(DFS(nx, ny))
                w[x][y]++;
        }
    }
    if(w[x][y]>=4)
        return 1;
    return 0;
}

int main()
{
    int T, cas=1;
    scanf("%d", &T);

    while(T--)
    {
        scanf("%d%d", &n, &m);
        for(int i=0; i<n; i++)
            scanf("%s", maps[i]);

        memset(w, 0, sizeof(w));
        memset(b, 0, sizeof(b));

        printf("Case %d:
", cas++);
        for(int i=0; i<n; i++)
        {
            for(int j=0; j<m; j++)
            {
                if(maps[i][j]=='.')
                {
                    memset(b, 0, sizeof(b));
                    memset(w, 0, sizeof(w));
                    DFS(i, j);
                    if(w[i][j]==4)
                        maps[i][j]='*';
                }
                printf("%c", maps[i][j]);
            }
            printf("
");
        }
    }
    return 0;
}