【暑期第二次训练赛】小火山的围棋梦想

快来打我* 2022-07-19 05:30 153阅读 0赞

## Problem H: 小火山的围棋梦想 ##

Time Limit: 1 Sec Memory Limit: 128 MB  
Submit: 190 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 ##

23 3\*\*\*\*.\*\*\*\*4 4.\*..\*.\*.\*.\*..\*..

## Sample Output ##

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

## HINT ##

用dfs做比较好，注意边缘上的被围住的“ . "符号不用变为” \* “。和围棋不完全一样。

样例输出样例输入可能不太清楚，可以打开下面的链接，没密码的比赛。题目还是挺好的。

#include<stdio.h>
    #include<iostream>
    #include<algorithm>
    #include<string.h>
    using namespace std;
    int px[4]= {1,-1,0,0};
    int py[4]= {0,0,1,-1};
    char map[30][30],vis[30][30];
    //bool check(int i,int j) {
    //	if(map[i][j]=='.'&&map[i+1][j]=='*'&&map[i-1][j]=='*'&&map[i][j+1]=='*'&&map[i][j-1]=='*')
    //		return true;
    //	return false;
    //}
    void dfs(int x,int y) {
    	vis[x][y]=1;
    	for(int l=0; l<4; l++) {
    		int nx=x+px[l];
    		int ny=y+py[l];
    		if(!vis[nx][ny]&&map[nx][ny]=='.') {
    			vis[nx][ny]=1;
    			dfs(nx,ny);
    		}
    	}
    }
    int main() {
    	int T,p=0;
    	scanf("%d",&T);
    	while(T--) {
    		int n,m,ans=0;
    		memset(vis,0,sizeof(vis));
    		scanf("%d%d",&n,&m);
    		for(int i=1; i<=n; i++) {
    			getchar();
    			for(int j=1; j<=m; j++) {
    				scanf("%c",&map[i][j]);
    			}
    		}
    		for(int i=1; i<=n; i++) {
    			for(int j=1; j<=m; j++) {
    				if((i==1||i==n||(i>1&&i<n&&(j==1||j==m)))&&map[i][j]=='.'&&!vis[i][j])
    					dfs(i,j);
    			}
    		}
    		printf("Case %d:\n",++p);
    		for(int i=1; i<=n; i++) {
    			for(int j=1; j<=m; j++) {
    				if(!vis[i][j]||map[i][j]=='*')
    					printf("*");
    				else
    					printf(".");
    			}
    			printf("\n");
    		}
    	}
    	return 0;
    }

[题目链接：http://acm.zzuli.edu.cn/zzuliacm/problem.php?cid=1158&pid=7][http_acm.zzuli.edu.cn_zzuliacm_problem.php_cid_1158_pid_7]

[Submit]: http://acm.zzuli.edu.cn/zzuliacm/submitpage.php?cid=1158&pid=7&langmask=4081
[Status]: http://acm.zzuli.edu.cn/zzuliacm/problemstatus.php?id=1908
[Web Board]: http://acm.zzuli.edu.cn/zzuliacm/bbs.php?pid=1908&cid=1158
[http_acm.zzuli.edu.cn_zzuliacm_problem.php_cid_1158_pid_7]: http://acm.zzuli.edu.cn/zzuliacm/problem.php?cid=1158&pid=7