本文主要是介绍深度搜索算法（c++），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
迷宫出口
一天Extense在森林里探险的时候不小心走入了一个迷宫，迷宫可以看成是由n * n的格点组成，每个格点只有2种状态， 0和1，前者表示可以通行后者表示不能通行。同时当Extense处在某个格点时，他只能移动到东南西北(或者说上下左 右)四个方向之一的相邻格点上，Extense想要从点A走到点B，问在不走出迷宫的情况下能不能办到。如果起点或者终 点有一个不能通行(为1)，则看成无法办到。
输入
第1行是一个正整数n (1 ≤ n ≤ 100)，表示迷宫的规模是n * n的。接下来是一个n * n的矩阵， 矩阵中的元素为0或者1。再接下来一行是4个整数ha la hb lb，描述A处在第ha行 第la列，B处 在第hb行 第lb列。
输出
能办到则输出“YES”，否则输出“NO”。
输入复制
3
0 1 1
0 0 1
1 0 0
1 1 3 3
输出复制
YES
#include <iostream>
#include <iomanip>
using namespace std;
int a[110][110];
int n;
int si,sj,ei,ej;
bool f = false;
int di[] = {0,1,0,-1};
int dj[] = {1,0,-1,0};
void aaa(int,int);
int main()
{cin>>n;for(int i = 0;i<n;i++){for(int j = 0;j<n;j++){cin>>a[i][j];}}cin>>si>>sj>>ei>>ej;si--;sj--;ei--;ej--;aaa(si,sj);if(f==true){cout<<"YES";}else{cout<<"NO";}return 0;
}
void aaa(int i,int j)
{if(i==ei&&j==ej){f = true;return;}a[i][j] = 2;for(int qqq = 0;qqq<4;qqq++){int ti = i+di[qqq];int tj = j+dj[qqq];if(ti>=0&&ti<n&&tj>=0&&tj<n&&a[ti][tj]==0&&f==false){aaa(ti,tj);}}return;
}数池塘
题目描述
农夫约翰的农场可以表示成N*M（1≤N≤100≤M≤100）个方格组成的矩形。由于 近日的降雨，在约翰农场上的不同地方形成了池塘。每一个方格或者有积水（'W'） 或者没有积水（'.'）。农夫约翰打算数出他的农场上共形成了多少池塘。一个池塘 是一系列相连的有积水的方格，每一个方格周围的四个方格都被认为是与这个方格 相连的。现给出约翰农场的图样，要求输出农场上的池塘数。
输入
第1行：由空格隔开的两个整数：N和M
第2..N+1行：每行M个字符代表约翰农场的一排方格的状态。每个字符或者是 'W'或者是'.'，字符之间没有空格。
输出
输出只有1行，输出约翰农场上的池塘数
输入复制
10 12
W . . . . . . . . W W .
. W W W . . . . . W W W
. . . . W W . . . W W .
. . . . . . . . . W W .
. . . . . . . . . W . .
. . W . . . . . . W . .
. W . W . . . . . W W .
W . W . W . . . . . W .
. W . W . . . . . . W .
. . W . . . . . . . W .
输出复制
13
#include <iostream>
#include <iomanip>
using namespace std;
char a[110][110];
int n,m;
int cnt = 0;
int di[4] = {0,1,0,-1};
int dj[4] = {1,0,-1,0};
void aaa(int,int);
int main()
{cin>>n>>m;for(int i = 0;i<n;i++){for(int j = 0;j<m;j++){cin>>a[i][j];}}for(int i = 0;i<n;i++){for(int j = 0;j<m;j++){if(a[i][j]=='W'){aaa(i,j);cnt++;}}}cout<<cnt;return 0;
}
void aaa(int i,int j)
{a[i][j] = '.';for(int qqq = 0;qqq<4;qqq++){int ti = i+di[qqq];int tj = j+dj[qqq];if(ti>=0&&ti<n&&tj>=0&&tj<m&&a[ti][tj]=='W'){aaa(ti,tj);}}return;
}数池塘（八方向）
题目描述
农夫约翰的农场可以表示成 N×M（1≤N,M≤100）个方格组成的矩形。 由于近日的降雨，在约翰农场上的不同地方形成了池塘。 每一个方格或者有积水（'W'）或者没有积水（'.'）。农夫约翰打算数出 他的农场上共形成了多少池塘。一个池塘是一系列相连的有积水的方格， 每一个方格周围的八个方格都被认为是与这个方格相连的。 现给出约翰农场的图样，要求输出农场上的池塘数。
输入
第 11 行：由空格隔开的两个整数：NN 和 MM；
第 2..N+1 行：每行 M 个字符代表约翰农场的一排方格的 状态。每个字符或者是'W'或者是'.'，字符之间没有空格
输出
输出只有1行，输出约翰农场上的池塘数。
输入复制
10 12
10 12
W . . . . . . . . W W .
. W W W . . . . . W W W
. . . . W W . . . W W .
. . . . . . . . . W W .
. . . . . . . . . W . .
. . W . . . . . . W . .
. W . W . . . . . W W .
W . W . W . . . . . W .
. W . W . . . . . . W .
. . W . . . . . . . W .
输出复制
3
#include <iostream>
#include <iomanip>
using namespace std;
char a[110][110];
int n,m;
int cnt = 0;
int di[] = {0,1,0,-1,1,-1,1,-1};
int dj[] = {1,0,-1,0,1,1,-1,-1};
void aaa(int,int);
int main()
{cin>>n>>m;for(int i = 0;i<n;i++){for(int j = 0;j<m;j++){cin>>a[i][j];}}for(int i = 0;i<n;i++){for(int j = 0;j<m;j++){if(a[i][j]=='W'){aaa(i,j);cnt++;}}}cout<<cnt;return 0;
}
void aaa(int i,int j)
{a[i][j] = '.';for(int qqq = 0;qqq<8;qqq++){int ti = i+di[qqq];int tj = j+dj[qqq];if(ti>=0&&ti<n&&tj>=0&&tj<m&&a[ti][tj]=='W'){aaa(ti,tj);}}return;
}奶牛和草丛
题目描述
奶牛Bessie计划好好享受柔软的春季新草。新草分布在 R 行 C列的牧场里。它想计算一下牧场中的草丛数量。
在牧场地图中，每个草丛要么是单个“#”，要么是有公共 边的相邻多个“#”。给定牧场地图，计算有多少个草丛。
例如，考虑如下5行6列的牧场地图；
. # . . . .
. . # . . .
. . # . . #
. . . . # #
. . . . . #
这个牧场有 3个草丛：一个在第一行，一个在第二列横跨 了二、三行，一个在第三行横跨了三、四、五行。
输入
第一行包含两个整数 R 和 C ，中间用 单个空格隔开。 接下来 R 行，每行 C 个字符，描述牧 场地图。字符只有“#”或“.”两种。 (1 ≤ R, C ≤ 100)
输出
输出一个整数，表示草丛数。
输入复制
5 6
. # . . . .
. . # . . .
. . # . . #
. . . . # #
. . . . . #
输出复制
3
#include <iostream>
#include <iomanip>
using namespace std;
char a[110][110];
int n,m;
int cnt = 0;
int di[] = {0,1,0,-1};
int dj[] = {1,0,-1,0};
void aaa(int,int);
int main()
{cin>>n>>m;for(int i = 0;i<n;i++){for(int j = 0;j<m;j++){cin>>a[i][j];}}for(int i = 0;i<n;i++){for(int j = 0;j<m;j++){if(a[i][j]=='#'){aaa(i,j);cnt++;}}}cout<<cnt;return 0;
}
void aaa(int i,int j)
{a[i][j] = '.';for(int qqq = 0;qqq<4;qqq++){int ti = i+di[qqq];int tj = j+dj[qqq];if(ti>=0&&ti<n&&tj>=0&&tj<m&&a[ti][tj]=='#'){aaa(ti,tj);}}return;
}晶 矿 的 个 数
题 目 描 述
在 某 个 区 域 发 现 了 一 些 晶 矿，已 经 探 明 这 些 晶 矿 总 共 有 分 为 两 类， 为红晶矿和黑晶矿。现在要统计该区域内红晶矿和黑晶矿的个数。
假设可以用二维地图m[][]来描述该区域，若m[i][j]为#表示该地点是 非晶矿地点，若m[i][j]为r表示该地点是红晶矿地点，若m[i][j]为b表 示该地点是黑晶矿地点。
一个晶矿是由相同类型的并且上下左右相通的晶矿点组成。现在给 你该区域的地图，求红晶矿和黑晶矿的个数。
输入格式
第一行为k，表示有k组测试输入。 每组第一行为n，表示该区域由 n*n个地点组成，
接下来n行，每行n个字符，表示该地点的类型。
输出格式
对每组测试数据输出一行，每行两个数字分别是红晶矿和黑晶矿的 个数，一个空格隔开。
样 例 输 入
样 例 输 出
2 2
1 2
#include <iostream>
#include <iomanip>
using namespace std;
char a[110][110];
int n;
int nn;
int cnthong[110],cnthei[110];
int di[4] = {0,1,0,-1};
int dj[4] = {1,0,-1,0};
void aaa(int,int);
void aaaa(int,int);
int main()
{cin>>nn;for(int k = 0;k<nn;k++){cin>>n;for(int i = 0;i<n;i++){for(int j = 0;j<n;j++){cin>>a[i][j];}}for(int i = 0;i<n;i++){for(int j = 0;j<n;j++){if(a[i][j]=='r'){aaa(i,j);cnthong[k]++;}}}for(int i = 0;i<n;i++){for(int j = 0;j<n;j++){if(a[i][j]=='b'){aaaa(i,j);cnthei[k]++;}}}}for(int i = 0;i<nn;i++){cout<<cnthong[i]<<" "<<cnthei[i]<<endl;}return 0;
}
void aaa(int i,int j)
{a[i][j] = '.';for(int qqq = 0;qqq<4;qqq++){int ti = i+di[qqq];int tj = j+dj[qqq];if(ti>=0&&ti<n&&tj>=0&&tj<n&&a[ti][tj]=='r'){aaa(ti,tj);}}return;
}
void aaaa(int i,int j)
{a[i][j] = '.';for(int qqq = 0;qqq<4;qqq++){int ti = i+di[qqq];int tj = j+dj[qqq];if(ti>=0&&ti<n&&tj>=0&&tj<n&&a[ti][tj]=='b'){aaa(ti,tj);}}return;
}这篇关于深度搜索算法（c++）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
