小火山 zzuli 1908 （围棋）

小火山的围棋梦想

 

Description

  小火山最近喜欢上了围棋。   对于围棋，其实小火山是一窍不通的。现在棋盘上，有很多小火山的棋子。 如果棋盘上有这样的一个位置， 那么这个位置也会变成小火山 的棋子；这样的位置是指小火山的棋子将该位置围起来。   现在，小火山想知道实际棋盘是什么样子的。 你快来帮帮他吧！

Input

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

Output

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

Sample Input

2 3 3 *** *.* *** 4 4 .*.. *.*. *.*. .*..

Sample Output

Case 1: *** *** *** Case 2: .*.. ***. ***. .*..

题解：dfs,没想到怎么判断棋子是否被围住，其实只要dfs看它能否走到边界就行，走不到边界肯定是被围住了，第一次dfs判断是否被围住，第二次dfs将该棋子变成 ' * ' .

#include<cstdio> #include<cstring> using namespace std; int t,n,m; bool flag; bool vis[40][40]; char map[40][40]; int dx[4]={1,0,-1,0}; int dy[4]={0,1,0,-1}; void dfs1(int a,int b){ int i; //i不能定义在主函数外 if (!flag) return ; for (i=0;i<4;i++){ int tx=a+dx[i]; int ty=b+dy[i]; if (map[tx][ty]=='*'||vis[tx][ty]) continue; if (tx<=0 || ty<=0 ||tx>=n-1||ty>=m-1){//边界 flag=false; return ; } vis[tx][ty]=true; dfs1(tx,ty); if (!flag) return ; } } void dfs2(int a,int b){ int i; for (i=0;i<4;i++){ int tx=a+dx[i]; int ty=b+dy[i]; if (map[a][b]=='*') continue; map[a][b]='*';//变成自己的棋子 dfs2(tx,ty); } } int main(){ int j,i,cas=1; scanf ("%d",&t); while (t--){ scanf ("%d%d",&n,&m); for (i=0;i<n;i++){ scanf ("%s",map[i]); } for (i=1;i<n-1;i++){ for (j=1;j<m-1;j++){ if (map[i][j]=='.'){ memset(vis,false,sizeof(vis));//注意初始化的位置 flag=true; dfs1(i,j); if (flag){ map[i][j]='*'; dfs2(i,j); } } } } printf ("Case %d:\n",cas++); for (i=0;i<n;i++) printf ("%s\n",map[i]); } return 0; }