搜索DFSBFS

本文主要是介绍搜索DFSBFS，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

红与黑

有一间长方形的房子，地上铺了红色、黑色两种颜色的正方形瓷砖。

你站在其中一块黑色的瓷砖上，只能向相邻（上下左右四个方向）的黑色瓷砖移动。

请写一个程序，计算你总共能够到达多少块黑色的瓷砖。

输入格式

输入包括多个数据集合。

每个数据集合的第一行是两个整数 WW 和 HH，分别表示 xx 方向和 yy 方向瓷砖的数量。

在接下来的 HH 行中，每行包括 WW 个字符。每个字符表示一块瓷砖的颜色，规则如下

1）‘.’：黑色的瓷砖；
2）‘#’：白色的瓷砖；
3）‘@’：黑色的瓷砖，并且你站在这块瓷砖上。该字符在每个数据集合中唯一出现一次。

当在一行中读入的是两个零时，表示输入结束。

输出格式

对每个数据集合，分别输出一行，显示你从初始位置出发能到达的瓷砖数(记数时包括初始位置的瓷砖)。

数据范围

$1\le W,H\le 20$

输入样例：

6 9 
....#. 
.....# 
...... 
...... 
...... 
...... 
...... 
#@...# 
.#..#. 
0 0

** 输出样例：**

45

---

AC代码:

1. BFS:

#include <bits/stdc++.h>
using namespace std;
///
const int N = 21;
char a[N][N];
int vis[N][N] = {0};
int res=1; //当前位置的黑砖 1 个 
int w,h; //h行  w列 
//
struct point{int x,y;point(){}point(int x,int y):x(x),y(y) {} //构造重载
};
void BFS(int r,int c){res=1;	//初始为1memset(vis,0,sizeof(vis)); //初始化全0  全为falsequeue<point> Q;Q.push(point(r,c));while(Q.empty()==false){ //队列不空 point tp = Q.front();Q.pop();//上 if(tp.x-1>=0 && vis[tp.x-1][tp.y] == false && a[tp.x-1][tp.y] == '.'){Q.push(point(tp.x-1,tp.y));vis[tp.x-1][tp.y] = true;res++;}//下 if(tp.x+1<h && vis[tp.x+1][tp.y] == false && a[tp.x+1][tp.y] == '.'){Q.push(point(tp.x+1,tp.y));vis[tp.x+1][tp.y] = true;res++;}//左 if(tp.y-1>=0 && vis[tp.x][tp.y-1] == false && a[tp.x][tp.y-1] == '.'){Q.push(point(tp.x,tp.y-1));vis[tp.x][tp.y-1] = true;res++;}//右 if(tp.y+1<w && vis[tp.x][tp.y+1] == false && a[tp.x][tp.y+1] == '.'){Q.push(point(tp.x,tp.y+1));vis[tp.x][tp.y+1] = true;res++;}}
} 
int main() {int posr,posc;while(cin>>w>>h){ //h列 w行if(w==0&&h==0) break;for(int i=0;i<h;i++) {for(int j=0;j<w;j++) {cin>>a[i][j];if(a[i][j] == '@'){posr=i;posc=j; //记录当前位置 }} }vis[posr][posc]=true; //初始位置被访问 BFS(posr,posc);printf("%d\n",res);}
} 

2. DFS:

#include <bits/stdc++.h>
using namespace std;
///
const int N = 21;
char a[N][N];
int vis[N][N] = {0};
int res=1; //当前位置的黑砖 1 个 
int w,h; //h行  w列 void DFS(int r,int c){//上 if(r-1>=0 && vis[r-1][c] == false && a[r-1][c] == '.'){vis[r-1][c] = true;res++;DFS(r-1,c);}//下 if(r+1<h && vis[r+1][c] == false && a[r+1][c] == '.'){vis[r+1][c] = true;res++;DFS(r+1,c);}//左 if(c-1>=0 && vis[r][c-1] == false && a[r][c-1] == '.'){vis[r][c-1] = true;res++;DFS(r,c-1);}//右 if(c+1<w && vis[r][c+1] == false && a[r][c+1] == '.'){vis[r][c+1] = true;res++;DFS(r,c+1);}} 
int main() {int posr,posc;while(cin>>w>>h){ //h列 w行res=1;memset(vis,0,sizeof(vis));if(w==0&&h==0) break;for(int i=0;i<h;i++) {for(int j=0;j<w;j++) {cin>>a[i][j];if(a[i][j] == '@'){posr=i;posc=j; //记录当前位置 }} }vis[posr][posc]=true; //初始位置被访问 DFS(posr,posc);printf("%d\n",res);}
} 

这篇关于搜索DFSBFS的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---