挑战程序设计竞赛——详解DFS及BFS

一.学会要用到的stl函数，Stack、Quene、Pair

1.Stack(DFS隐式的用到，并与Queue对比记忆)

头文件==#include==

stack常用函数

push() 入栈
top() 获得栈顶元素
pop() 弹出栈顶元素
empty() 可以检测stack内是否为空，返回true为空，返回false为非空
size() 返回stack内元素的个数

Quene（BFS中用到）

头文件==#inclde==

queue常用函数

push() 在队尾插入一个元素
pop() 删除队列第一个元素
empty() 可以检测queue内是否为空，返回true为空，返回false为非空
size() 返回队列中元素个数
**front() ** 返回队列中的第一个元素
back() 返回队列中最后一个元素

[^]: Stack和Queue的函数中==，增删判空都一样，只有查不一样== ，其中Stack用top（），Queue用front（）、back（）

Pair（BFS中用到，也可以用结构体，顺便提一句，Pair也是用结果体实现）

头文件==#include ==

Pair常用函数

p1.first; // 返回对象p1中名为first的公有数据成员
p1.second; // 返回对象p1中名为second的公有数据成员

例一 Lake Counting (POJ No.2386) >

由于最近的降雨，在 Farmer John 的田地的各个地方积水，由 N x M (1 <= N <= 100; 1 <= M <= 100) 正方形组成的矩形表示。每个方格包含水（‘W’）或旱地（‘.’）。农夫约翰想弄清楚他的田地里形成了多少池塘。池塘是一组相连的正方形，里面有水，其中一个正方形被认为与其所有八个邻居相邻。

给定农民约翰的田地图，确定他有多少池塘。

限制条件

N，M <= 100

样例

输入

10 12
W........WW.
.WWW.....WWW
....WW...WW.
.........WW.
.........W..
..W......W..
.W.W.....WW.
W.W.W.....W.
.W.W......W.
..W.......W.

输出

代码如下：

#include <bits/stdc++.h>//万能头文件
/*
#include <iostream>
*/ 
using namespace std;
const int maxl = 105;

int dir[8][2] = {{1, -1}, {1, 0}, {1, 1}, {0, -1}, {0, 1}, {-1, 1}, {-1, 0}, {-1, -1}};//斜左下、下、斜右下、左 、右、斜右上、上、斜左上 
char mp[maxl][maxl];
bool book[maxl][maxl];//是否检查过 
int n, m, ans = 0;

void dfs(int x, int y){//把相连的水都标记 
	book[x][y] = true;
	
	for (int i = 0; i < 8; i++){
		int nx = x + dir[i][0];
		int ny = y + dir[i][1];
		if (nx >= 0 && nx < n && ny >= 0 && ny < m && mp[nx][ny] == 'W' && !book[nx][ny]){
			dfs(nx, ny);
		}
	}
}
int main(){
	cin >> n >> m;//输入 
	for (int i = 0; i < n; i++)
	    for (int j = 0; j < m; j++){
			cin >> mp[i][j];
		}
    
    memset(book, 0, sizeof(book));//初始化 
    
	for (int i = 0; i < n; i++)
	   	for (int j = 0; j < m; j++){
		   	if(mp[i][j] == 'W' && !book[i][j]){//是水并且没来过 
			   	dfs(i, j); 
			   	ans++;
			   }
		}
	cout << ans;
	return 0;
	}

例二迷宫的最短路径

给定一个大小为 N \times MN×M 的迷宫，由通道和墙壁组成。

每一步可以向相邻的上下左右四个方向移动。

请求出起点到终点的最小步数。本题保证从起点一定能走到终点。

# 表示墙壁，不可走。 . 表示通道，可走。S 表示起点。G 表示终点。

限制条件

N, M <= 100

样例

输入

10 10
#S######.#
......#..#
.#.##.##.#
.#........
##.##.####
....#....#
.#######.#
....#.....
.####.###.
....#...G#

输出

代码如下

版本一使用pair

#include <bits/stdc++.h>
using namespace std;

const int maxl = 100;

int n, m, sx, sy, gx, gy, ans = 0;
int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};//下、上、右、左 
char mp[maxl][maxl];//存储地图 
bool book[maxl][maxl];//检查是否来过 
typedef pair<int, int> P;//存放点（x，y） 
int d[maxl][maxl];//存放据起始点经过的步数 

int bfs(){
	queue<P> que;
	que.push(P(sx, sy));
	
	while (!que.empty()){
		P p = que.front();
		que.pop();
		
		if(p.first == gx && p.second == gy)    break;
		
		for (int i = 0; i < 4; i++){
			int nx = p.first + dir[i][0];
			int ny = p.second + dir[i][1];
			
			if (nx >= 0 && nx < n &&  ny >= 0 && ny < m && mp[nx][ny] != '#' && !book[nx][ny]){
				que.push(P(nx, ny));(mp[nx][ny] == '.' || mp[nx][ny] == 'G')  等价于  mp[nx][ny] != '#'
				book[nx][ny] = true; 
				d[nx][ny] = d[p.first][p.second] + 1;
			}
		}
			
	}
	
	return d[gx][gy];
}

int main(){
	cin >> n >> m;
	for (int i = 0; i < n; i++)
	    for (int j = 0; j < m; j++){
			cin >> mp[i][j];
			if(mp[i][j] == 'S'){
				sx = i;
				sy = j;
			}
			if(mp[i][j] == 'G'){
				gx = i;
				gy = j;
			}
}
	
	memset(book, 0, sizeof(book));
	memset(d, 0, sizeof(d));
		
	cout << bfs();
	return 0;
}

版本二使用结构体

#include <bits/stdc++.h>
using namespace std;

const int maxl = 100;

int n, m, gx, gy, sx, sy;
char mp[maxl][maxl];
bool book[maxl][maxl];
int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

typedef struct node{
	int x, y;
	int d;	//省了记录路径的数组 
	node (int x, int y, int d){    //构造函数 
		this->x = x;
		this->y = y;
		this->d = d;
	}
}node;

int dfs(){
	queue<node> que;
	node nod(sx, sy, 0);
	que.push(nod);
	book[sx][sy] = true;
	
	while (!que.empty()){
		node t = que.front();
		que.pop();
		
		if (t.x == gx && t.y == gy)
		return t.d;
		
		for (int i = 0; i < 4; i++){
			int nx = t.x + dir[i][0];
			int ny = t.y + dir[i][1];
			if (nx >= 0 && nx < n && ny >= 0 && ny < m && mp[nx][ny] != '#' && !book[nx][ny]){
				que.push(node(nx, ny, t.d + 1));
				book[nx][ny] = true;
	    	}
		}
		
	}
	return 0;
}
int main(){
	cin >> n >> m;
	for (int i = 0; i < n; i++)
	    for (int j = 0; j < m; j++){
			cin >> mp[i][j];
			if (mp[i][j] == 'S'){
				sx = i;
				sy = j;
			}
			if (mp[i][j] == 'G'){
				gx = i;
				gy = j;
			}
}

    cout << dfs();
}