【zzuliOJ】1908 - 小火山的围棋梦想（dfs）

FishWang

发布于 2025-08-27 10:04:43

10500

代码可运行

运行总次数：0

代码可运行

点击打开题目

1908: 小火山的围棋梦想

Time Limit: 1 Sec Memory Limit: 128 MB Submit: 197 Solved: 46 Submit Status Web Board

Description

小火山最近喜欢上了围棋。

对于围棋，其实小火山是一窍不通的。现在棋盘上，有很多小火山的棋子。如果棋盘上有这样的一个位置，那么这个位置也会变成小火山

的棋子；这样的位置是指小火山的棋子将该位置围起来。

现在，小火山想知道实际棋盘是什么样子的。你快来帮帮他吧！

Input

输入第一行是一个整数T（T <= 30), 表示一共有T组数据。

每组数据，第一行为两个整数n， m(1 <= n, m <= 25), 随后一个n*m的矩阵代表棋盘，其中"."是代表没放棋子的位置， "*"代表小火山的棋子。

Output

对于每组数据输出一个n*m的棋盘，代表实际的棋盘。

Sample Input

3 3

***

* .*

***

4 4

.*..

*.*.

.*..

Sample Output

Case 1:

***

Case 2:

.*..

***.

.*..

HINT

Source

zzuli

跑dfs时，把 . 的位置都标记成@，符合条件的位置改为*

代码如下：

#include <stdio.h>
#include <cstring>
#include <algorithm>
using namespace std;
#define CLR(a,b) memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
#define LL long long
char mapp[30][30];
int mx[4] = {0,0,1,-1};
int my[4] = {1,-1,0,0};
int h,w;
bool flag;
void dfs1(int x,int y)
{
    mapp[x][y] = '@';
    for (int i = 0 ; i < 4 ; i++)
    {
        int nx,ny;
        nx = x + mx[i];
        ny = y + my[i];
        if (nx < 1 || nx > h || ny < 1 || ny > w)
        {
            flag = false;
            continue;
        }
        if (mapp[nx][ny] != '*' && mapp[nx][ny] != '@')
            dfs1(nx,ny);
    }
}
void dfs2(int x,int y)
{
    mapp[x][y] = '*';
    for (int i = 0 ; i < 4 ; i++)
    {
        if (mapp[x+mx[i]][y+my[i]] != '*')
            dfs2(x+mx[i],y+my[i]);
    }
}
int main()
{
    int u;
    int Case = 1;
    scanf ("%d",&u);
    while (u--)
    {
        scanf ("%d %d",&h,&w);
        for (int i = 1 ; i <= h ; i++)
            scanf ("%s",mapp[i]+1);
        for (int i = 1 ; i <= h ; i++)
        {
            for (int j = 1 ; j <= w ; j++)
            {
                if (mapp[i][j] == '.')
                {
                    flag = true;
                    dfs1(i,j);
                    if (flag)
                        dfs2(i,j);
                }
            }
        }
        printf ("Case %d:\n",Case++);
        for (int i = 1 ; i <= h ; i++)
        {
            for (int j = 1 ; j <= w ; j++)
            {
                if (mapp[i][j] == '@')
                    printf (".");
                else
                    printf ("%c",mapp[i][j]);
            }
            printf ("\n");
        }
    }
    return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-08-26，如有侵权请联系 cloudcommunity@tencent.com 删除

scanf