【信息学竞赛-算法竞赛 讲解】搜索

搜索是C++中一种常用的算法，在很多题里面都是通用的（当然，有可能是暴力的时候用）

一、深度优先搜索（DFS）

深度优先搜索：(Depths First Search)简称深搜(DFS)，是一种完全建立在递推和递归的基础上的暴力搜索方法。

通过递推和递归的运行机制，用较少的代码就能够实现全状态枚举，且通过回溯机制，可以很容易的维护一些需要延后处理的数据。比用纯暴力的循环枚举更容易实现。

深搜的原理就是“一条路走到头，走到走不动了再倒回来从岔路接着走”。明显就和递归的原理一样。也可以比喻为“单刀深入”，相当于整个搜索过程就只有一个人在里面跑。

由于深搜是建立在递归的基础上的，所以需要对递归的运行原理有深刻的认识，否则会很容易出错。

• 迷宫
• 联通块问题
• 全排列问题
• 选数问题

洛谷B3625 迷宫寻路（点击传送）

• 题目大意：给你一张n*m的地图，# 表示墙，. 表示空地。从图的左上点(1,1)开始走，问能否走到右下点(n,m)
• 题目思路：

  我们通过递归函数dfs访问 (x,y)，若不是终点，则尝试往四个方向中的一个前进。【符合DFS思路）

  那么这个 dfs 就可以这么写：

  • 排除非法情况，比如坐标越界和遇到障碍物；
  • 如果访问过，则跳过；
  • 如果没访问过，继续处理并标记已访问；【如果不标记就会死循环】
  • 如果得到答案，退出程序；
  • 否则向四个方向继续扩展。

• AC代码：

#include<cstdio>
#include<algorithm>

using namespace std;

const int maxn = 105;
int n, m;
bool map[maxn][maxn]; //地图，不能走的点(即已走过的或墙)为true

void input() {//输入函数
	scanf("%d %d", &n, &m);

	//双重循环输入地图
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			char in;
			scanf(" %c", &in); //用scanf有提行的输入字符记得在 %c前加空格，避免读入到换行
			if (in == '#') {
				map[i][j] = true; //如果是墙标记为不能走了 
			}
		}
	}
	return;
}

void DFS(int x, int y) { //(x,y)为现在走到的坐标 
	if (x < 1 || x > n || y < 1 || y > m || map[x][y] == true) { //判断(x,y)是否越界或(x,y)是否可以走到，统称点(x,y)是否非法 
		return;//如果这个点非法，就回退到上一个点 
	}
	if (x == n && y == m) { //判断是否到达终点 
		printf("Yes");
		exit(0); //输出并结束程序 
	}
	map[x][y] = true; //走过这个点了标记上不能再走了，如果不标记会死循环 

	//向四个方向前进 
	DFS(x + 1, y);
	DFS(x - 1, y);
	DFS(x, y + 1);
	DFS(x, y - 1);

	return;
}

int main() {
	input();
	DFS(1, 1);
//如果能走到，在DFS函数中已经输出Yes并结束程序了;不能走到会在回退到起点后并退出DFS，然后在这里输出No 
	printf("No");
	return 0;
}

洛谷T564913 闭合曲线面积（点击传送）

• 题目大意：在一个10*10的二维数组中，用1表示墙，用0表示空地，求被墙围起来的空地的面积
• 题目思路：把*看成围墙，我们是想进入围墙的人，但是怎么也进不了，于是我们就在围墙的周围乱走，把能不进围墙就走到的地方走个遍，统计围墙外的点数。然而她就是这么无懈可击。删掉围墙。剩下的就是被围住的面积了。从地图四周每个点开始进行一次深搜得到墙外面积，被围住的面积 = 总地图面积 - 围墙占地 - 墙外面积
• AC代码：

#include<cstdio>

using namespace std;

const int maxn = 11;
bool map[maxn][maxn]; //地图，不能走的点(即已走过的或墙)为true 
int wall, Out_Of_Wall; //墙的占地面积，墙外的面积 

void input() {
	//双重循环输入地图 
	for (int i = 1; i <= 10; ++i) {
		for (int j = 1; j <= 10; ++j) {
			int in;
			scanf("%d", &in);
			if (in == 1) { //如果是一(即是墙)，标记为不能走的点 
				map[i][j] = true;
				++wall; //累加墙的面积 
			}
		}
	}
}

void DFS(int x, int y) {
	if (x < 1 || x > 10 || y < 1 || y > 10 || map[x][y] == true) { //走到非法的点(超出地图边界或走过的点或墙) 
		return;
	}

	map[x][y] = true;
	++Out_Of_Wall; //标记后累加墙外的点 

	//向四个方向前进 
	DFS(x + 1, y);
	DFS(x - 1, y);
	DFS(x, y + 1);
	DFS(x, y - 1);
	return;
}

int main() {
	input();
	for (int i = 1; i <= 10; ++i) { //从地图四边开始查找 
		DFS(1, i);
		DFS(10, i);
		DFS(i, 1);
		DFS(i, 10);
	}
	printf("%d", 100 - wall - Out_Of_Wall); //被围住的面积 = 总地图面积 - 围墙占地 - 墙外面积
	return 0;
}

洛谷P1706 全排列问题（点击传送）

• 题目大意：给出一个整数n，用1~n中所有数字进行排列，并输出每一种排列方式，每个数字场宽为5。
• 题目思路：先定义两个数组，一个是用来存放答案的ans[maxn]，一个是用来标记该数是否用过use[maxn]。

  我们可以先写一个用于输出的函数print()，每当深搜找到一个符合条件的解时，则print()一下，输出这个解（注意题目输出要求）。

  接下来就是写深搜函数DFS()了：先判断是否算了n位，如果算完了n位（即得出了一种情况），就print()一下。

  如果没有填满，则开始循环，在循环中先判断当前填的数是否用过，如果没有，则填入，搜索下一位。

• AC代码：

#include<cstdio>

using namespace std;

const int maxn = 10;
int n;
bool use[maxn]; //标记第i个数是否已被使用过

void input() {
	scanf("%d", &n);
	return;
}

int ans[maxn]; //记录答案
void print() {
	for (int i = 0; i < n; ++i) {
		printf("%5d", ans[i]); //场宽为 5
	}
	printf("\n");
	return;
}

void DFS(int No) { //No 用于计数算到了第几位
	if (No == n) { //得到了n位数的一种排列
		print(); //调用输出函数
	}
	for (int i = 1; i <= n; ++i) {
		if (use[i] == false) { //第i个数未被使用
			use[i] = true; //标记
			ans[No] = i; //记录第i位答案
			DFS(No + 1); //计算下一位
			use[i] = false; //回溯，取消标记，以便后续计算使用
		}
	}
	return;
}

int main() {
	input();
	DFS(0); //由于第28行 DFS(No + 1) ，所以从0开始，否则会少算一位答案
	return 0;
}