欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

深搜

程序员文章站 2022-03-26 11:31:23
...

有一个长方形的房间,覆盖了正方形的磁砖。每块磁砖的颜色,要么是红色,要么是黑色。一名男子站在一块黑色的磁砖上。他可以从一块磁砖移至相邻四块磁砖中的某一块。但是,他不允许在红色磁砖上移动,他只允许在黑色磁砖上移动。

编写一个程序,使得他允许重复上述的移动,判断他所能到达的黑色磁砖的数量。

  输入
   输入由多个数据集组成。数据集的起始行包含了两个正整数 W 和 H;W 和 H 分别是 x- 和 y- 方向的磁砖数量。W 和 H 不超过 20 。 

在数据集中,还有 H 行,每行包含了 W 个字符。每个字符按如下方式表示一块磁砖的颜色。

‘.’ - 一块黑色的磁砖

‘#’ - 一块红色的磁砖

‘@’ - 一名男子,站在一块黑色磁砖上 (在一个数据集中,恰好出现一次)

以包含两个 0 的一行,表示输入结束。

  输出
   对于每个数据集,程序应当输出一行,包含他从初始磁砖所能抵达的磁砖数量 (包括初始磁砖自身)。 

#include"iostream"
#include"cstring"
#include"algorithm"
using namespace std;
const int maxn = 30;
bool vst[maxn][maxn];
char pic[maxn][maxn];
int dic[4][2]={0,1,0,-1,1,0,-1,0};
int n,m,sum;
bool cheak(int x,int y)
{
if(!vst[x][y] && pic[x][y] == ‘.’ && x >= 0 && y >= 0 && x <= m && y <=n)
{
return 1;
}
return 0;
}

void dfs(int x,int y)
{
vst[x][y]=1;
sum ++;
for(int i = 0;i < 4;i ++)
{
int cx=x+dic[i][0];
int cy=y+dic[i][1];
if(cheak(cx,cy))
{
dfs(cx,cy);
}
}
}
int main()
{
while(cin >> n >> m &&(n && m))
{
memset(vst,0,sizeof(vst));
memset(pic,0,sizeof(pic));
for(int i = 0;i < m; i++)
{
cin >> pic[i];
}
int xx,yy;
for(int i = 0;i < m;i ++)
{
for(int j = 0;j < n;j ++)
{
if(pic[i][j] == ‘@’)
{
xx=i;
yy=j;
}
}
}
sum = 0;
dfs(xx,yy);
cout<<sum<<endl;
}
return 0;
}

深搜与广搜区别就是搜索方式不同了

程序上与广搜的写法差不多
但要在dfs里使用递归,然后便能达成效果
大致的过程
主函数中两层for循环找到@也就是初始位置
调用dfs函数,用dic数组模拟移动后坐标
并通过cheak判断是不是我们要寻找的‘.’
如果是就再次调用dfs自身,sum累计
如果不是,就在for循环中寻找下一个坐标

深搜