C/C++ 之 深搜 与 回溯

深搜

可以简单地理解为递归 [手动滑稽]

深搜 简称 为深度优先搜索（dfs）

简单的来说，就像细胞分裂

1变2 ， 2变4 ，4变8 ...

举一个既简单的例子：

把例题也放出来吧：

来源：一本通

跳转：信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)

1317：【例5.2】组合的输出

时间限制: 1000 ms         内存限制: 65536 KB
提交数: 32273     通过数: 15827
【题目描述】
排列与组合是常用的数学方法，其中组合就是从n个元素中抽出r个元素(不分顺序且r≤n)，我们可以简单地将n个元素理解为自然数1，2，…，n，从中任取r个数。

现要求你用递归的方法输出所有组合。

例如n＝5，r＝3，所有组合为：

1 2 3   1 2 4   1 2 5   1 3 4   1 3 5   1 4 5   2 3 4   2 3 5   2 4 5   3 4 5

【输入】
一行两个自然数n、r(1 
很简单
 
这道题我们按照常规的思路理一遍
 
第一项  从1开始，一直到n;
 
第二项  因为题目明确点名不能重复，所以要从2开始，一直到n
 
第三项  和第二项原理一样，从3到n
 
所以现在我们脑子里就有了一颗（不要写错别字哦）大树
 
 
可以暂停一下，理一下思路；
 
 
然后我们用黑客专用语言（瞎BB）说一下；
 
i = 1; 
 
第一项  从i开始，一直到n;
 
第二项 从++i开始，一直到n
 
第三项  从i+2开始，一直到n
 
... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .. .. . . ... ... ...  ..
 
... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .. .. . . ... ... ...  ..
 
... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .. .. . . ... ... ...  ..
 
第r项    从i+r-1开始，一直到n
 
 
现在你脑海里这颗大树就是深搜的主要思路了
 
恭喜你
 
好的，我们看一下代码
 
#include 

using namespace std;

int n , r;
const int N = 30;
int res[N];

void dfs(int step , int last){//step就是层数（项数），last就是上一个数；
	if(step > r){
		for(int i=1 ;i<=r ;i++){
			cout << "  " << res[i];//这里题目要求
		}
		cout << endl;
		return;
	}
	for(int i=last + 1 ; i <= n ;i++){
		res[step]=i;
		dfs( step + 1 , i );
	}
}

int main(){
	cin >> n >> r;
	dfs(1,0);
	return 0;
}
 
嘿嘿，我就知道你没看懂
 
下面我来详解一下 算法之最 —— 深搜
 
上面已经驹过例子了，所以我们直接讲  代码思路  （不是深搜思路哦）；
 
首先一个循环，i  就是我刚刚说的  i ，没错 此 i 正是 彼 i；
 
然后节点就是n
 
因为是递归的思路，所以我们每经过一个数，层数（项数）就++；
 
然后上一个数就是  i  了
 
于此，我们函数的两个变量就有了；
 
然后我们定义一个数组来存储每层的数
 
所以我们循环里的  res[step]=i;  就有了；
 
然后我们需要一个特判
 
这个就真心简单了
 
如果我们的层数 大于 题目所输入的层数
 
就说明这次深搜成功了（这条路通了）
 
我们先循环输出之前每一层的数字，（这里有一个小点：每次深搜的数都会覆盖前面的数）
 
然后   再返回上一层；
 
 
最后看主函数；
 
int 是定义变量
 
然后记得  每一行  都要加分号  ；
 
然后 cin 是输入 记得头文件是iostream
 
这么难得C++高级知识大家应该都不知道吧   [狗头保命]
 
 
我想 ， 现在大家应该就都明白深搜的具体思路和模板了；
 
 
接下来看一道  比较简单  的  新  题型题：
 
（来源：一本通）
 
跳转： 信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)
 
 
1215：迷宫

时间限制: 1000 ms         内存限制: 65536 KB
提交数: 43870     通过数: 13430
【题目描述】
一天Extense在森林里探险的时候不小心走入了一个迷宫，迷宫可以看成是由n×n的格点组成，每个格点只有2种状态，.和#，前者表示可以通行后者表示不能通行。同时当Extense处在某个格点时，他只能移动到东南西北(或者说上下左右)四个方向之一的相邻格点上，Extense想要从点A走到点B，问在不走出迷宫的情况下能不能办到。如果起点或者终点有一个不能通行(为#)，则看成无法办到。

【输入】
第1行是测试数据的组数k，后面跟着k组输入。每组测试数据的第1行是一个正整数n(1≤n≤100)，表示迷宫的规模是n×n的。接下来是一个n×n的矩阵，矩阵中的元素为.或者#。再接下来一行是4个整数ha,la,hb,lb，描述A处在第ha行, 第la列，B处在第hb行, 第lb列。注意到ha,la,hb,lb全部是从0开始计数的。

【输出】
k行，每行输出对应一个输入。能办到则输出“YES”，否则输出“NO”。

【输入样例】
2
3
.##
..#
#..
0 0 2 2
5
.....
###.#
..#..
###..
...#.
0 0 4 0
【输出样例】
YES
NO
 
很简单
 
思路主要就是
 
从起点开始
 
每次深搜右四个方向
 
然后定义一个数组
 
如果已经走过这个坐标了，就变成1；
 
然后特判下一个落脚点能不能走有三个条件
 
1.是否越界
 
2.之前有没有走过
 
3.这里是不是墙
 
 
然后又是代码的白嫖时间：
 
#include 
#include 

using namespace std;

const int N = 110;
char s[N][N];
int tp[N][N];
int n;
bool flag = false;
int ha , la , hb , lb;
int xy[4][2] = { {1,0}, {-1,0}, {0,1}, {0,-1} };//这样就不用写4个特判了

void dfs ( int x , int y) {
	for(int i=0; i < 4; i++){
		int x_num = x + xy[i][0];
		int y_num = y + xy[i][1];
		
	if( x_num == hb && y_num == lb){
			flag = true;
			return;
	} else{
		if(s[x_num][y_num] == '.' && tp[x_num][y_num] != 1 && x_num >= 0 && y_num >=0 && x_num < n && y_num < n){
			tp[x_num][y_num] = 1;
			dfs(x_num , y_num);
		}
	}
	}
}


int main(){
	int b;
	cin >> b;
	for(int q =1; q <= b; q++){
		cin >> n;
		for(int i = 0; i < n; i++){//题目是从0开始的
			for(int j =0; j < n; j++){
				cin >> s[i][j];
			}
		}
		memset(tp , 0 , sizeof(tp));//这里要清零一下
		flag = false;
		cin >> ha >> la >> hb >> lb;
		tp[ha][la] = 1;
		tp[hb][lb] = 1;
		if( s[ha][la] == '#' || s[hb][lb] == '#'){
			cout << "NO" << endl;
		}else{
			dfs( ha , la);	
			if( flag ){
				cout << "YES" << endl;
			}else{
				cout << "NO" << endl;
			}		
			
		}
		
	}
	return 0;
}
 
是的，如果你已经看到这里了，那么说明你已经是一名  高手  了；
 
 
那么我们再来一道题练练手：
 
来源：一本通
 
跳转：信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)
 
1216：红与黑

时间限制: 1000 ms         内存限制: 65536 KB
提交数: 25346     通过数: 10260
【题目描述】
有一间长方形的房子，地上铺了红色、黑色两种颜色的正方形瓷砖。你站在其中一块黑色的瓷砖上，只能向相邻的黑色瓷砖移动。请写一个程序，计算你总共能够到达多少块黑色的瓷砖。

【输入】
包括多组数据。每组数据的第一行是两个整数W和H，分别表示x方向和y方向瓷砖的数量。W和H都不超过20。在接下来的H行中，每行包括W个字符。每个字符表示一块瓷砖的颜色，规则如下:

1）‘.’：黑色的瓷砖；

2）‘#’：白色的瓷砖；

3）‘@’：黑色的瓷砖，并且你站在这块瓷砖上。该字符在每组数据中唯一出现一次。

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

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

【输入样例】
6 9 
....#.
.....#
......
......
......
......
......
#@...#
.#..#.
0 0
【输出样例】
45
 
不多解释，和刚刚那题简直就是  一模一样  啊
 
如果你再不懂，那我就真的无语了呀；
 
 
#include 
#include 

using namespace std;

const int N=30;
int n,m;
int xy[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
int tp[N][N];
char s;
int kpip[N][N];
int xx,yy;
int sum=1;

void dfs(int x,int y){
    for(int i=0;i<4;i++){
        int x_num = x+xy[i][0];
        int y_num = y+xy[i][1];
        if(x_num >= 0 && x_num < n & y_num >= 0 && y_num < m &&  (! tp[x_num][y_num]) && (kpip[x_num][y_num])  ){ 
            tp[x_num][y_num] = 1;
            sum ++;
            dfs(x_num , y_num);
        }
    }

}

int main () {
	
    while(cin >> m >> n , m , n){
  
        sum = 1;
        for(int i=0 ; i < n ; i++){
            for(int j=0; j < m; j++){
                cin >> s;
				if(s == '#'){
                	kpip[i][j] = 0;
				}else if(s == '.'){
              	  	kpip[i][j] = 1;	
				} else if(s == '@'){
                    xx = i;
                    yy = j;
                    kpip[i][j] = 1;
                }
            }
        }
         tp[xx][yy] = 1;
        dfs(xx , yy);
        
        cout << sum << endl;       
        memset(tp , 0 , sizeof(tp) );
        memset(kpip , 0 , sizeof(kpip)) ;  

    }
 
    return 0;
}
 
 
所以既然你已经看到这里了，
 
不妨点个赞？
 
嘿嘿拜拜