2021-04-25 11:36 已编辑河南理工大学 C++

关注

BFS与DFS

BFS(宽度优先搜索)

宽度优先搜索算法（又称广度优先搜索算法）是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。

他并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。

举例：

由橙色位置出发，进行BFS：

灰色位置表示已经走过，橙色标示当前位置

首先进行第一步：

已经走过的位置，不需要再走了

进行第二步：

同上，状态继承，进行第三步：

进行第四步，到达终点，当前步数表示最小步数：

对于一个迷宫而言，我们要进行的步骤是一样的。

蓝色是起点，红色是终点，黑色为障碍物。

第一步，我们可以走以下几步：

接下来依次为：

当我们走到第十步时，走到了终点，因此，从起点到终点最少的步数即为10步。

接下来看一道基础的例题（HDU1242）Rescue：

Problem Description

Angel was caught by the MOLIGPY! He was put in prison by Moligpy. The prison is described as a N * M (N, M <= 200) matrix. There are WALLs, ROADs, and GUARDs in the prison.

Angel's friends want to save Angel. Their task is: approach Angel. We assume that "approach Angel" is to get to the position where Angel stays. When there's a guard in the grid, we must kill him (or her?) to move into the grid. We assume that we moving up, down, right, left takes us 1 unit time, and killing a guard takes 1 unit time, too. And we are strong enough to kill all the guards.

You have to calculate the minimal time to approach Angel. (We can move only UP, DOWN, LEFT and RIGHT, to the neighbor grid within bound, of course.)

Input

First line contains two integers stand for N and M.

Then N lines follows, every line has M characters. "." stands for road, "a" stands for Angel, and "r" stands for each of Angel's friend.

Process to the end of the file.

Output

For each test case, your program should output a single integer, standing for the minimal time needed. If such a number does no exist, you should output a line containing "Poor ANGEL has to stay in the prison all his life."

Sample Input

7 8
#.#####.
#.a#..r.
#..#x...
..#..#.#
#...##..
.#......
........

Sample Output

这个题大概的意思就是求从字符a出发，到达字符r的最少时间，其中 . 代表空地，#代表墙，x代表守卫，每杀死一个守卫我们就需要消耗一秒的时间。

这个题可以用BFS直接求解，代码如下：

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
using namespace std;
#define MAXN 510
char str[MAXN][MAXN];//用来储存地图 
int vis[MAXN][MAXN];//用来标记已经走过的地点 
int n,m;
struct name
{
	int x;
	int y;
	int step;
};
bool operator <(name i,name j){//对走过的地点顺序进行排序 
	return i.step>j.step;
}
int d[4][2]={1,0,-1,0,0,1,0,-1};//表示行走的四个方向，顺序为右，左，上，下 

int BFS(int sx,int sy,int ex,int ey)
{
	memset(vis,0,sizeof(vis));
	priority_queue<name>que;//使用队列用来储存上一步走过的地点 
	name e1,e2;
	e1.x=sx,e1.y=sy,e1.step=0;
	que.push(e1);//输入起点 
	vis[sx][sy]=1;
	int ans=-1; 
	int i;
	while(!que.empty()){//当队列为空时，即表示我们已经把所有的能走的地点都走了一遍 
		e1=que.top();//将队列第一个地点的信息赋给e1； 此时e1即表示上一步走过的地点的信息 
		que.pop();
		if(e1.x==ex && e1.y==ey){//对这个地点进行判断，看是否是是终点 
			ans=e1.step;
			break;
		}
		for(i=0;i<4;i++){//如果e1不是终点，那么对e1的上下左右进行判断，如果可以走，那么就将信息储存在队列中 
			e2.x=e1.x+d[i][0];
			e2.y=e1.y+d[i][1];
			if(e2.x<0 || e2.x>=n || e2.y<0 || e2.y>=m) continue;//对边界进行判断，如果超出边界，则不进行保存 
			if(vis[e2.x][e2.y]==1) continue;//如果当前位置已经走过，那么就不进行保存 
			if(str[e2.x][e2.y]=='#') continue;//如果是墙壁,不进行保存 
			if(str[e2.x][e2.y]=='x') e2.step=e1.step+2;//如果是守卫的话，需要消耗两个单位时间 
			else e2.step=e1.step+1;//如果是空地,一个单位时间 
			que.push(e2);//将地点存入队列 
			vis[e2.x][e2.y]=1;//降低点进行标记 
		}
	}
	if(ans==-1){
		printf("Poor ANGEL has to stay in the prison all his life.\n");
	}
	else{
		printf("%d\n",ans);
	}
	
}
int main()
{
	int i,j;
	while(~scanf("%d %d",&n,&m)){
		for(i=0;i<n;i++){ 
			scanf("%s",str[i]);
		}
		int sx,sy,ex,ey;
		for(i=0;i<n;i++){//找寻起点和终点 
			for(j=0;j<m;j++){
				if(str[i][j]=='a') sx=i,sy=j;
				if(str[i][j]=='r') ex=i,ey=j;
			}
		}
		BFS(sx,sy,ex,ey);//开始BFS
	}
	
	return 0;
}

从代码中可以看出，我们使用BFS的步骤为：

1.对地图信息进行保存

2.找到起点和终点信息

3.从起点开始，对所走过的每一步进行判断

4.如果走的这一步可行，那么储存这一步的信息，并标记这个位置，表示不会再走到这个位置

5.如果不可行，那么就不进行操作

6.找到终点

以上，即为BFS的功能。

DFS(深度优先搜索)

DFS的目的是要达到被搜索结构的叶结点。其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次。

DFS的使用基础为递归，当我们顺着一个节点向下走时，如果走不下去了，就回溯，如果上一个节点还有其他的节点，那么我们就会对这个节点再进行搜索。

对于下面这个图

首先我们将从第一个节点开始出发，然后搜索第二个节点，

因为第二个节点下面还有第四个节点，因此我们继续向下搜索，

第四个节点下面已经没有其他节点，因此我们回溯到第二个节点

第二个节点下面还有第五个节点，因此我们搜索第五个节点

然后继续回溯，到第一个节点，

接下来就搜索第三个节点，第五个节点

当再次回溯到第一个节点时，已经没有其他的节点可进行搜索，因此搜索的过程到此结束，DFS也到此结束。

上面就是DFS的功能，DFS是对所有可能的结果进行一次彻底的搜索，这样会保证不会有任何情况会被遗漏。

接下来看一道例题（Red and Black）：

There is a rectangular room, covered with square tiles. Each tile is colored either red or black. A man is standing on a black tile. From a tile, he can move to one of four adjacent tiles. But he can't move on red tiles, he can move only on black tiles.

Write a program to count the number of black tiles which he can reach by repeating the moves described above.

Input

The input consists of multiple data sets. A data set starts with a line containing two positive integers W and H; W and H are the numbers of tiles in the x- and y- directions, respectively. W and H are not more than 20.

There are H more lines in the data set, each of which includes W characters. Each character represents the color of a tile as follows.

'.' - a black tile
'#' - a red tile
'@' - a man on a black tile(appears exactly once in a data set)

Output

For each data set, your program should output a line which contains the number of tiles he can reach from the initial tile (including itself).

Sample Input

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

Sample Output

45 59 6 13

这个题的大概意思就是给你一个起点，你能够走到多少个地点。

其中 ' . '是空地，#是墙壁，@是起点。

接下来看一下代码，思想和BFS类似：

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define clr(a) memset(a,0,sizeof(a))

const int MAXN = 1e5+10;
const int INF = 0x3f3f3f3f;
const int N = 30;

int n,m,sum;
char mapp[N][N];//储存地图 
int vis[N][N];//标记位置 
int dx[4] = {1,-1,0,0};//四个行走方向 
int dy[4] = {0,0,1,-1};

bool check(int x,int y){//检测不能走通的条件 
    if(x<0||x>=n||y<0||y>=m||mapp[x][y]=='#'){
        return false;
    }
    else return true;
}
void DFS(int x,int y){
    if(!check(x,y)||vis[x][y]){//如果不能走通，那么直接返回 
        return ;
    }
    else{
        sum++; 
        int fx,fy;
        for(int i=0;i<4;i++){//在此节点的基础上，再对周围四个节点进行判断 
            vis[x][y] = true;
            fx = x + dx[i];
            fy = y + dy[i];
            DFS(fx,fy);//此处使用递归求解 
        }
    }
}
int main(){
    while(scanf("%d%d",&m,&n)!=EOF&&(n||m)){
        clr(mapp);clr(vis);
        sum = 0;
        for(int i=0;i<n;i++){
            scanf("%s",mapp[i]);
        }
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(mapp[i][j] == '@'){
                    DFS(i,j);
                    break;
                }
            }
        }
        printf("%d\n",sum);
    }
    return 0;
}

从代码中我们可以看出，DFS的使用方法为：

1.找出起点

2.对起点四个方向的状态进行判断，如果是空地，就进行递归，继续对这四个方向的位置的四周进行判断，如果不是空地，就结束递归

3.输出结果

DFS与BFS有很多相似的地方，不过BFS求的是最短路，DFS求的是方案数，我们可以根据题目要求选择这两种方法。