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

深度优先搜索(DFS)C++

程序员文章站 2022-06-11 12:41:17
...

深度优先搜索(DFS)

深度优先搜索是搜索的手段之一。它是从某个状态开始,不断转移状态,直到无法转移,然后退回到前一步的状态,继续转移到其他状态,如此不断重复,直至找到最终解。

深度优先搜索(DFS)C++
深度优先搜索(隐式的)利用了栈进行计算,栈(Stack)支持push和pop两种操作,数据元素后进先出。

例题:Lake Counting (POJ No.2386)

题目描述

有一个大小为N * M 的园子,雨后积起了水。八连通的积水被认为是连接在一起的。请求出园子里总共有多少水洼?(八连通指的是下图中相对 W 的 * 的部分)

***
*W*
***

限制条件:
N,M <= 100

样例输入

N=10, M=12
园子如下图(‘W’表示积水,’.'表示没有积水)

W . . . . . . . . WW .
. WWW . . . . .WWW
. . . . WW . . . WW .
. . . . . . . . . WW .
. . . . . . . . . W . .
. . W . . . . . . . W .
. W . W . . . . . WW .
W . W . W . . . . . W .
. W . W . . . . . . W .
. . W . . . . . . . W .

样例输出

3

题目分析

从任意的W开始,不停地把邻接的部分用‘.’代替。1次DFS后与初始的这个W连接的所有W就都被替换成了‘.’,因此直到图中不再存在W为止,总共进行 DFS 的次数就是答案了。8个方向共对应了8种状态转移,每个格子作为DFS的参数至多被调用一次,所以复杂度为 O( 8×N×M) = O(N×M)

代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAX_N = 10001;
int N,M; 
char field[MAX_N][MAX_N+1];	//园子 

//现在位置( x, y ) 
void dfs(int x, int y){
	//将现在所在位置替换为 . 
	field[x][y] = '.';
	
	//循环遍历移动的8个方向 
	for(int dx = -1; dx<=1; dx++){
		for(int dy = -1; dy<=1; dy++){
			// 向x方向移动dx,向y方向移动dy,移动的结果为(nx, ny) 
			int nx = x + dx, ny = y + dy;
			// 判断(nx, ny)是不是在园子内,以及是否有积水 
			if(0<=nx && nx < N && 0<=ny && ny < M && field[nx][ny] =='W')
				dfs(nx,ny);
		}
	} 
	return ;
} 


int main(){
	cin >> N >> M;
	int res = 0;
	
	for(int i=0; i<N; i++){
		for(int j=0; j<M; j++)
			cin >> field[i][j];
	} 
	
	for(int i=0; i<N; i++){
		for(int j=0; j<M; j++)
			if(field[i][j] == 'W'){
				//从有W的地方开始dfs 
				dfs(i,j);
				res++; 
			}
	} 
	
	cout << res << endl;
	return 0;
}