小火山的围棋梦想多校训练2（小火山专场）Poj（DFS）

daydayupacm 2021-08-27 原文

http://acm.zzuli.edu.cn/zzuliacm/problem.php?id=1908

分析：一开始很简单暴力的想着只要判断\’*\’是否能围成一个圈就好，但是发现好难写啊。。在比赛结束后，有人教我只需判断外围一圈的点就好，若它是\’.\’则对它进行标记。最后只需将未被标记的\’.\’变成\’*\’即可。

#include <stdio.h>
#include <algorithm>
#include <string.h>
#define maxn 30
using namespace std;

int dir[4][2] = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
char maps[maxn][maxn];
int v[maxn][maxn];
int n, m;

void DFS(int x, int y)
{
    v[x][y] = 1;

    for(int i=0; i<4; i++)
    {
        int nx = x + dir[i][0];
        int ny = y + dir[i][1];

        if(nx>=0 && nx<n && ny>=0 && ny<m && maps[nx][ny]==\'.\' && !v[nx][ny])
             DFS(nx, ny);
    }
}
int main()
{
    int T, cnt=1;

    scanf("%d", &T);

    while(T --)
    {
        scanf("%d %d", &n, &m);

        for(int i=0; i<n; i++)
            scanf("%s", maps[i]);

        memset(v, 0, sizeof(v));

        for(int i=0; i<n; i++)
        {
            for(int j=0; j<m; j++)
            {
                if(i!=0 && j!=0 && i!=n-1 && j!=m-1) continue;

                if(maps[i][j]==\'.\' && !v[i][j])
                    DFS(i, j);
            }
        }

        for(int i=0; i<n; i++)
        {
            for(int j=0; j<m; j++)
            {
                if(!v[i][j] && maps[i][j]==\'.\')
                    maps[i][j]=\'*\';
            }
        }

        printf("Case %d:\n", cnt++);

        for(int i=0; i<n; i++)
            printf("%s\n", maps[i]);

    }
    return 0;
}