[数据结构与算法]红与黑（POJ1979）DFS+记忆化搜索详细题解

红与黑（POJ1979）

1. 题目

有一个长方形的房间，覆盖着方形的瓷砖。每个瓷砖都是红色或黑色。一个人站在一块黑色的瓷砖上。从瓷砖，他可以移动到四个相邻的瓷砖之一。但他不能在红色瓷砖上移动，他只能在黑色瓷砖上移动。
编写一个程序，通过重复上述动作来计算他可以达到的黑色瓷砖
数量。
输入

输入由多个数据集组成。数据集以包含两个正整数 W 和 H 的行开始：W 和 H 分别是 x 方向和 y 方向的瓷砖数量。W 和 H 不超过 20。
数据集中有更多的行，每个行都包含 W
字符。每个字符表示瓦片的颜色如下。
'. - 黑色瓷砖 “#” - 红色瓷砖 “@” - 黑色瓷砖上的人（在数据集中正好显示一次）输入的末端由两个零组成的行指示。

输出

对于每个数据集，您的程序应输出一条包含他从初始磁贴（包括自身）中可以到达的磁贴数量的行。
示例输入

6 9
…#.
…#
…
…
…
…
…
#@…#
.#…#.
11 9
.#…
.#.#######.
.#.#…#.
.#.#.###.#.
.#.#…@#.#.
.#.#####.#.
.#…#.
.#########.
…
11 6
…#…#…#…
…#…#…#…
…#…#…###
…#…#…#@.
…#…#…#…
…#…#…#…
7 7
…#.#…
…#.#…
###.###
…@…
###.###
…#.#…
…#.#…
0 0
样例输出
4加粗样式5
59
6
13

2.题目分析

简化题目含义我们知道：

1.地图上是"."时可以走且只能走一次。
2.地图上是"#"时不可走。
3.地图上是"@"为起始位置。
4.可以往四个方向走
5.不可超出边界

3.题解

对1.的处理：
当任意方向是".“时可以走，且需要记录已经走过的位置
对2.的处理：
当任意方向是”#“时不可以走
对3.的处理：
因为输入时是逐个输入，则我们输入的字符为”@"时记录当前的x与y
对4.的处理：
因为要执行多个方向，重复动作，可以用DFS遍历各个方向。
对5.的处理：
x+1<=20,x-1>=1;y+1<=20,y-1>=1;（我们选择从下标1开始）
对地图的处理：
二维数组
对方向的解释：
假如当前位置为a [x] [y];则：
a[x-1][y]为其向上位置；
a[x+1][y]为其向下位置；
a[x][y-1]为其向左位置；
a[x][y+1]为其向右位置；
对记录位置的处理：
使用二维数组记录走过的位置，0为未走过，1为已走过
对于走过多少黑块的分析：
每前往过一个方向即为走过一次黑块，且需要将该走过的位置记录为1

代码

#include<iostream>
#include<cstring>
using namespace std;
char a[21][21];
bool b[21][21];
int E,h,w;
void search(int x,int y)
{	E++;
	if(x-1>=1&&a[x-1][y]=='.'&&b[x-1][y]==0)//不超过边界且下一方向为"."且没走过
	{
	
		b[x-1][y]=1;//置为1
		search(x-1,y);
	}
	if(y-1>=1&&a[x][y-1]=='.'&&b[x][y-1]==0)//不超过边界且下一方向为"."且没走过
	{
		b[x][y-1]=1;//置为1
		search(x,y-1);
	}
	if(x+1<=w&&a[x+1][y]=='.'&&b[x+1][y]==0)//不超过边界且下一方向为"."且没走过
	{
		b[x+1][y]=1;//置为1
		search(x+1,y);
	}
	if(y+1<=h&&a[x][y+1]=='.'&&b[x][y+1]==0)//不超过边界且下一方向为"."且没走过
	{
		b[x][y+1]=1;//置为1
		search(x,y+1);
	}
	return;
}
int main()
{
	int x,y;
	while(cin>>w>>h)
	{
		if(h==0&&w==0)
			break;
		for(int j=1;j<=h;j++)
		{
			for(int i=1;i<=w;i++)
			{
				
				cin>>a[i][j];
				if(a[i][j]=='@')//记录位置
				{
					x=i;
					y=j;
				}
			}
		}
		b[x][y]=1;
		E=0;
		search(x,y);
		cout<<E<<endl;//输出
		memset(a,0,sizeof(a));//格式化地图，统统置为0
		memset(b,0,sizeof(b));
	}
}