HNCU1103：红与黑(DFS)

180 阅读 0 评论 119 点赞

我是靠谱客的博主成就火车，这篇文章主要介绍HNCU1103：红与黑(DFS)，现在分享给大家，希望可以做个参考。

题目描述

小明站在一个矩形房间里，这个房间的地面铺满了地砖，每块地砖的颜色或是红色或是黑色。小明一开始站在一块黑色地砖上，并且小明从一块地砖可以向上下左右四个方向移动到其他的地砖上，但是他不能移动到红色地砖上，只能移动到黑色地砖上。
请你编程计算小明可以走到的黑色地砖最多有多少块。

输入格式

输入包含多组测试数据。
每组输入首先是两个正整数W和H，分别表示地砖的列行数。（1<=W,H<=20）
接下来H行，每行包含W个字符，字符含义如下：
‘.’表示黑地砖；
‘#’表示红地砖；
‘@’表示小明一开始站的位置，此位置是一块黑地砖，并且这个字符在每组输入中仅会出现一个。
当W=0，H=0时，输入结束。

输出

对于每组输入，输出小明可以走到的黑色地砖最多有多少块，包括小明最开始站的那块黑色地砖。

样例输入

6 9
....#.
.....#
......
......
......
......
......
#@...#
.#..#.
11 9
.#.........
.#.#######.
.#.#.....#.
.#.#.###.#.
.#.#..@#.#.
.#.#####.#.
.#.......#.
.#########.
...........
11 6
..#..#..#..
..#..#..#..
..#..#..###
..#..#..#@.
..#..#..#..
..#..#..#..
7 7
..#.#..
..#.#..
###.###
...@...
###.###
..#.#..
..#.#..
0 0

样例输出

45
59
6
13

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<cstdio>
int dis[4][2]={{1,0},{0,1},{0,-1},{-1,0}};
char ci[21][21];
int w,h,s;

void dfs(int x,int y){
	int nx,ny,k;
	s++;
	ci[x][y]='#';//标记走过的路 防止重复搜 
	for( k=0;k<4;k++){
		nx=x+dis[k][0];
		ny=y+dis[k][1];
		if(nx>=0&&ny>=0&&nx<h&&ny<w&&ci[nx][ny]=='.')//判断的是标记后的下一个位置属性 
			dfs(nx,ny);//若能继续搜 则继续搜 否则退回前一个坐标，继续搜
			           //相当与能dfs就入栈，不能就出栈，再操作栈顶元素（继续搜）
					   // 所以nx ny始终等于能继续往下搜才进行上下左右操作； 
			
	}
	return; 	
}
int main(){
	while(scanf("%d%d",&w,&h)&&(w||h)){
	 	s=0;

		for( int i=0;i<h;i++)
		     scanf("%s",ci[i]);
		   
		for( int i=0;i<h;i++)
		   for(int  j=0;j<w;j++)
		   	if(ci[i][j]=='@')
		   	  dfs(i,j);
		printf("%dn",s);
   
	}
	return 0;  
}

//办法2

复制代码

//源代码源于网络 稍加修改 
#include<cstdio> 
#include<cstring> 
using namespace std;
 
const int maxn=20+5;

const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
bool a[maxn][maxn],vis[maxn][maxn];
int w,h,ans=0;
 
bool can(int xx,int yy)
{
	if (xx<1||xx>h||yy<1||yy>w||!a[xx][yy]||vis[xx][yy]) return false;
	return true;
}
 
void dfs(int xx,int yy)
{
	vis[xx][yy]=true;//标记走过的路 
	ans++;
	for (int i=0;i<4;i++)
	{
		xx+=dx[i];
		yy+=dy[i];
		if (can(xx,yy)) //每次判断的是下一个位置是否能搜，即vis为false 所以想要回到前一个位置继续判断需要进行1，2操作，而办法1则不同 
		 
		dfs(xx,yy);
		xx-=dx[i];  //1 
		yy-=dy[i];  //2 
    }
    return;
}
 
int main()
{
	char ch;
	int xx,yy;
	while(scanf("%d%d",&w,&h)==2&&w)
	{
		ans=0;
		memset(a,0,sizeof(a));//清空数组 
		memset(vis,0,sizeof(vis));//清空数组 
		scanf("%c",&ch);
		for (int i=1;i<=h;i++)
		{
			for (int j=1;j<=w;j++)
			{
				scanf("%c",&ch);
				if (ch=='.') a[i][j]=1;
				else if (ch=='@')
				{
					xx=i;
					yy=j;
			    }
		    }
		    scanf("%c",&ch);
	    }
	    dfs(xx,yy);
	    printf("%dn",ans);
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
//源代码源于网络 稍加修改 
#include<cstdio> 
#include<cstring> 
using namespace std;
 
const int maxn=20+5;

const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
bool a[maxn][maxn],vis[maxn][maxn];
int w,h,ans=0;
 
bool can(int xx,int yy)
{
	if (xx<1||xx>h||yy<1||yy>w||!a[xx][yy]||vis[xx][yy]) return false;
	return true;
}
 
void dfs(int xx,int yy)
{
	vis[xx][yy]=true;//标记走过的路 
	ans++;
	for (int i=0;i<4;i++)
	{
		xx+=dx[i];
		yy+=dy[i];
		if (can(xx,yy)) //每次判断的是下一个位置是否能搜，即vis为false 所以想要回到前一个位置继续判断需要进行1，2操作，而办法1则不同 
		 
		dfs(xx,yy);
		xx-=dx[i];  //1 
		yy-=dy[i];  //2 
    }
    return;
}
 
int main()
{
	char ch;
	int xx,yy;
	while(scanf("%d%d",&w,&h)==2&&w)
	{
		ans=0;
		memset(a,0,sizeof(a));//清空数组 
		memset(vis,0,sizeof(vis));//清空数组 
		scanf("%c",&ch);
		for (int i=1;i<=h;i++)
		{
			for (int j=1;j<=w;j++)
			{
				scanf("%c",&ch);
				if (ch=='.') a[i][j]=1;
				else if (ch=='@')
				{
					xx=i;
					yy=j;
			    }
		    }
		    scanf("%c",&ch);
	    }
	    dfs(xx,yy);
	    printf("%dn",ans);
    }
    return 0;
}