hpu 1087 KACA的围棋入门

问题 J: KACA的围棋入门

时间限制: 1 Sec 内存限制: 128 MB

题目描述

KACA从小就有一个成为围棋高手的梦想，然而他对围棋的棋路一窍不通。

为了体验围棋的乐趣，他在一个棋盘上摆了若干个白字和黑子，他规定黑子不能吃白子，但是白子可以吃黑子。也就是说，若棋盘上有某些黑子没有"气"(被白子完全围住或因为达到边界)，则应当把黑子拿掉。反之若某些白子没有"气"(被黑子完全围住或达到边界)，则不需要拿掉。

现在以'#'代表白子，以'@'代表黑子，以'.'代表空棋盘，KACA想要知道按照这种规则处理之后的棋盘是什么状态。

输入

多组测试数据。

第一行是两个整数n，m(1 <= n, m <= 20),分别代表棋盘的行数和列数。

下面有一个n*m的矩阵代表棋盘，其中'#'代表白子，'@'代表黑子，'.'代表空棋盘。

输出

对于每组数据先输出一行"Case *:"代表第*组测试。

然后输出一个n*m的矩阵代表处理之后的棋盘。

样例输入

3 3
.#.
#@#
.#.
4 3
.#.
#@#
#@#
.#.
2 2
@@
@@

样例输出

Case 1:
.#.
#.#
.#.
Case 2:
.#.
#.#
#.#
.#.
Case 3:
..
..

思路：dfs一波；

从‘.’字符开始搜索，搜到的@符号就是不能移除的，搜索到@后，把@转换其他字符成没有搜索的@移除，#不变；

注意数据*

@@@@
@##@
@##@
@@@@
结果：
....
.##.
.##.
....

.@@@
@##@
@##@
@@@
结果：
.@@@
@##@
@##@
@@@

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<string.h>
using namespace std;
char a[30][30];
int n,m;
void dfs(int x,int y)
{
	for(int dx=-1;dx<=1;dx++)
	{
		for(int dy=-1;dy<=1;dy++)
		{
		    int nx=x+dx;
			int ny=y+dy;
			if(dy*dx==0)
			{
				if(nx<=n && nx>=1 && 1<=ny && ny<=m && a[nx][ny]=='.')
				{
					a[nx][ny]='!';
					dfs(nx,ny);
				}
				else if(1<=nx && nx<=n && 1<=ny && ny<=m && a[nx][ny]=='@')
				{
					a[nx][ny]='*';
					dfs(nx,ny);
				}
			}
		}
	}
	return;
}
int main()
{
	int p=0,i,j;
	while(scanf("%d %d",&n,&m)!=EOF)
	{
		p++;
		memset(a,0,sizeof(a));
		for(i=1;i<=n;i++)
		{
			getchar();
			for(j=1;j<=m;j++)
			{
				scanf("%c",&a[i][j]);
			}
		}
		for(i=1;i<=n;i++)
		{
			for(j=1;j<=m;j++)
			{
				if(a[i][j]=='.')
				{
					dfs(i,j);
				}
			}
		}
		printf("Case %d:\n",p);
		for(i=1;i<=n;i++)
		{
			for(j=1;j<=m;j++)
			{
				if(a[i][j]=='!' || a[i][j]=='@')
					printf(".");
				else if(a[i][j]=='*')
					printf("@");
				else printf("%c",a[i][j]);
			}
			printf("\n");
		}
	}
	return 0;
}