深搜

深搜的定义

深搜是一种对数串或图形进行遍历的算法。它会从起点像树状图一样向下进行探索，如果发现不能到达目标解，那就返回到上一个节点，然后从另一条路开始走到底 ，这种尽量往深处走的概念即是深度优先的概念。回溯是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。

深度优先搜索是对图进行搜索的算法，目的也都是从起点开始搜 索直到到达指定顶点（终点）。深度优先搜索会沿着一条路径不断往下搜索直到不能再继续为止，然后再折返，开始搜索下一条候补路径。

经典例题

1、寻找师傅 已知妖怪洞穴是一个N*N的正方形，其中有一些假山堵路。

输入：第一行是一个正整数N（2<N<10）,后面包含N*N行由0，1，2组成的矩阵，其中0表示可以走，1表示假山，2表示师傅的位置。

输出：如果悟空和八戒可以救出师傅就输出YES，否则就输出NO。

代码如下：

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int G[105][105],vis[105][105];
  4. int n;
  5. bool f = false;
  6. int dx[5] = {-1,0,1,0},dy[5] = {0,1,0,-1};
  7. void dfs(int x,int y){
  8.     if(G[x][y] == 2){
  9.         f = true;
  10.         return ;
  11.     }
  12.     for(int i=0;i<4;i++){
  13.         int xx = x+dx[i];
  14.         int yy = y+dy[i];
  15.         if(xx>=0 && xx<n && yy>= 0 && yy<n &&
  16.         G[xx][yy] != 1 && vis[xx][yy] == 0){
  17.             vis[xx][yy] = 1;
  18.             dfs(xx,yy);
  19.             vis[xx][yy] = 0;
  20.         }
  21.     }
  22. }
  23. int main(){
  24.     cin>>n;
  25.     for(int i=0;i<n;i++){
  26.         for(int j=0;j<n;j++){
  27.             cin>>G[i][j];
  28.         }
  29.     }
  30.     if(G[0][0] == 1){
  31.         cout<<"NO"<<endl;
  32.         return 0;
  33.     }else if(G[0][0] == 2){
  34.         cout<<"YES"<<endl;
  35.         return 0;
  36.     }else{
  37.         vis[0][0] = 1;
  38.         dfs(0,0);
  39.         if(f) cout<<"YES"<<endl;
  40.         else cout<<"NO"<<endl;
  41.         return 0;
  42.     }
  43.     return 0;
  44. }

2、传送门（逃生路径）

观音有一件法宝，叫做传送门，我们可以通过这件法宝从妖怪洞穴出去，为了保密，观音把这件法宝放在了一个妖怪洞穴，我们只要找到那个洞穴就可以出去了。观音已经把放法宝洞穴的坐标告诉我了，我们需要编程确定一下是否能到达那个洞穴就行了。

唐老大：空空，听紧箍咒和编程你选一个吧。

空空：你…(吐血三升)，你把样例先告诉我。

输入：第一行包含一个正整数N(1<n<30）表示迷宫的长和宽，下面N行，每行有N个数字，其中1表示可以走，0表示死路。接下来两行分别表示悟空和师傅所在洞穴坐标和传送门所在洞穴坐标。

输出：如果传送门位置和悟空所在位置相同，输出YES，如果无法到达传送门，输出NO，否则就输出所有可能的路径。

代码如下：

  1. #include <bits/stdc++.h>
  2. using namespace  std;
  3. const int MAXN = 35;
  4. int G[MAXN][MAXN];
  5. int vis[MAXN][MAXN];
  6. struct JGT{
  7.     int x,y;
  8. }p[1000];
  9. int dx[4]={-1,0,1,0};
  10. int dy[4]={0,1,0,-1};
  11. int n,sx,ex,sy,ey;  
  12. bool f = false;  
  13. void dfs(int x ,int y,int idx);  
  14. int main(){
  15.     cin >> n;
  16.     for(int i = 1; i <= n; i++){
  17.         for(int j = 1;j<=n;j++){
  18.             cin >> G[i][j];
  19.         }
  20.     }
  21.     cin >> sx >> sy >> ex >> ey ;
  22.     if(sx == ex && sy == ey) {
  23.         cout << "YES";
  24.         return 0;
  25.     }
  26.     vis[sx][sy]= 1;
  27.     p[0].x = sx;
  28.     p[0].y = sy;
  29.     dfs(sx,sy,1);
  30.     if(!f) cout << "NO";
  31.     return 0;
  32. }
  33. void dfs(int x ,int y,int idx){
  34.     if(x == ex && y == ey){
  35.         printf("(%d,%d)",p[0].x,p[0].y);
  36.         for(int k = 1;k < idx; k++){
  37.             printf("->(%d,%d)",p[k].x,p[k].y);
  38.         }
  39.         f = true;
  40.         return;
  41.     }
  42.     for(int i = 0 ;i < 4; i++){
  43.         int xx = x + dx[i];
  44.         int yy = y + dy[i];
  45.         if( xx >= 1 && xx <= n && 
  46.             yy >= 1 && yy <= n &&
  47.             G[xx][yy] && !vis[xx][yy]){
  48.                 vis[xx][yy] = 1; 
  49.                 p[idx].x = xx;
  50.                 p[idx].y = yy;
  51.                 dfs(xx ,yy ,idx+1);    
  52.                 vis[xx][yy] = 0;
  53.         }
  54.     }
  55. }

3、帮助红烧鱼

最近天气炎热，人鱼王国水位下降陆地露出海面，把王国分成了几个部分，国王的命令无法传达给公民，让红烧鱼国王感觉非常苦恼，所以国王想要请悟空帮忙给各个水域传递一个消息。

虽然人鱼王国不大，但是如果悟空每个地方都去一次就会耽误很长时间，影响取经大业，所以悟空决定先计算一下陆地把人鱼王国分成了几部分。

输入：第一行包含两个正整数N和M(1<N,M<30）表示人鱼王国的长和宽，下面是一个N行M列的二维数组，其中1表示陆地，0表示海水。

输入：一个整数a,表示陆地把海域分成的份数（斜着方向不算连通）。

代码如下：

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int G[31][31],n,m;
  4. int dx[5] = {-1,0,1,0},dy[5] = {0,1,0,-1};
  5. void dfs(int x,int y){
  6.     for(int i=0;i<4;i++){
  7.         int xx = x+dx[i];
  8.         int yy = y+dy[i];
  9.         if(xx >= 0 && xx < n && yy >= 0 && yy<m &&G[xx][yy] == 0){
  10.             G[xx][yy] = 1;
  11.             dfs(xx,yy);
  12.         }
  13.     }
  14. }
  15. int main(){
  16.     cin>>n>>m;
  17.     for(int i=0;i<n;i++){
  18.         for(int j=0;j<n;j++){
  19.             cin>>G[i][j];
  20.         }
  21.     }
  22.     int res = 0;
  23.     for(int i=0;i<n;i++){
  24.         for(int j=0;j<m;j++){
  25.             if(G[i][j] == 0){
  26.                 G[i][j] = 1;
  27.                 dfs(i,j);
  28.                 res++;
  29.             }
  30.         }
  31.     }
  32.     cout<<res;
  33.     return 0;
  34. }

4、国王的神器

最近天气炎热，人鱼王国水位下降陆地露出海面，把王国分成了几个部分，国王的命令无法传达给公民，让红烧鱼国王感觉非常苦恼，所以国王想要请悟空帮忙给各个水域传递一个消息。

虽然人鱼王国不大，但是如果悟空每个地方都去一次就会耽误很长时间，影响取经大业，所以悟空决定先计算一下陆地把人鱼王国分成了几部分。

红烧鱼国王拿出了祖传神器（水管），他可以使斜对角的海域连通，这样悟空就可以少通知一些地方了，真是个不错东西，我们一起来计算一下使用神器后，悟空需要通知几个海域。

gY-QmamvQDdnIyVpXp3_b.png 输入：第一行包含两个正整数N和M(1<N,M<30）表示人鱼王国的长和宽，下面是一个N行M列的二维数组，其中1表示陆地，0表示海水。

输入：一个整数a,表示陆地把海域分成的份数。

代码如下：

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int G[31][31],n,m;
  4. void dfs(int x,int y){
  5.     for(int i=-1;i<=1;i++){
  6.         for(int j=-1;j<=1;j++){
  7.             int xx = x+i;
  8.             int yy = y+j;
  9.             if(xx >= 0 && xx < n 
  10.             && yy >= 0 && yy<m &&
  11.             G[xx][yy] == 0){
  12.                 G[xx][yy] = 1;
  13.                 dfs(xx,yy);
  14.             }
  15.         }
  16.     }
  17. }
  18. int main(){
  19.     cin>>n>>m;
  20.     for(int i=0;i<n;i++){
  21.         for(int j=0;j<n;j++){
  22.             cin>>G[i][j];
  23.         }
  24.     }
  25.     int res = 0;
  26.     for(int i=0;i<n;i++){
  27.         for(int j=0;j<m;j++){
  28.             if(G[i][j] == 0){
  29.                 G[i][j] = 1;
  30.                 dfs(i,j);
  31.                 res++;
  32.             }
  33.         }
  34.     }
  35.     cout<<res;
  36.     return 0;
  37. }

4、