昆明专业网站营销,众筹网站建设方案模板,微信链接的微网站怎么做的,南京雨花台区做网站一、概念
深度优先搜索#xff08;Deep First Search, DFS#xff09;是一种用于遍历或搜索树或图的算法。这种策略沿着树的深度遍历树的节点#xff0c;尽可能深地搜索树的分支。
二、关键步骤
选择起点#xff1a;根据题目要求#xff0c;选择一个或多个节点作为搜索…一、概念
深度优先搜索Deep First Search, DFS是一种用于遍历或搜索树或图的算法。这种策略沿着树的深度遍历树的节点尽可能深地搜索树的分支。
二、关键步骤
选择起点根据题目要求选择一个或多个节点作为搜索的起点。 递归搜索从起点开始递归地访问每个节点的所有未访问的邻接节点。 回溯当到达一个节点且这个节点没有未访问的邻接节点时递归过程将回溯尝试其他可能的路径。 记录状态在递归前后正确地记录和恢复状态如访问状态、路径记录等是非常重要的。
三、代码模板
以下题为例说明关于深搜的几个模板 ①看能不能到达 ②能到达几次 ③连通块几个区域
1744 迷宫
有 1 个 n×n 的迷宫方格在方格内“0”表示可以通行“1”表示是障碍物不能通行在nn位置有一个宝箱。现在有个人在左上角 1 , 1 的位置他在迷宫内可以向当前位置的上、下、左、右四个方向行走能不能在迷宫里走到宝箱位置 nn 。注意测试数据保证起点和终点均为“0”走的过程不能走出迷宫。
输入描述 输入第一行为 n2 ≤n≤10 表示 n×n 的方格接下来有 n 行每行 n 个整数 0 表示可以行走1 表示不能行走每个整数之间有个空格。
输出描述 如果可以走到终点输出“YES”否则输出“NO”
样例输入 1 3 0 0 1 1 0 0 0 1 0 样例输出 1 YES
题目分析 首先我们输入nn行n列的数据【根据不同题目可能输入的数据存到字符串数组】 然后标记开始的位置【比如此题中开始位置就是 11即一行一列的位置】同时明确终点位置就是n,n【即n行n列】 然后开始搜索构建搜索函数dfs这个函数中我们会走四个方向所以使用两个一维数组表示四个方向坐标的改变的值 或者大家可以使用二维数组我们还要构建一个标记数组以下代码使用的是book数组来标记 函数中我们首先判断当前坐标是不是终点如果是终点就停止搜索【根据题目分析有些题目不能终止而是去计数】 然后再判断四个方向【不同题目方向的数目不同】计算新的落脚点 判断新的落脚点【nx,ny】是不是符合要求此题中需要满足三个条件①不越界②没标记③是可以通行的 如果可以通行则标记这个新的落脚点继续下一步的搜索
#includebits/stdc.h
using namespace std;
int n,a[15][15],dx[4]{-1,1,0,0},dy[4]{0,0,-1,1},book[15][15]; //左右上下
bool flag;
void dfs(int x,int y){if(x n y n){flag true;return ;}for(int i0;i4;i){int nx xdx[i],nyydy[i];//出界 标记 if(nx0nxn ny0nyn book[nx][ny]0 a[nx][ny]0){book[nx][ny]1;dfs(nx,ny);}}
}
int main(){cin n;for(int i1;in;i){for(int j1;jn;j){cin a[i][j];}}book[1][1]1;dfs(1,1);if(flag) coutYES;else cout NO;return 0;
}
同样的我们可以完成下面题目
2936 八个方向
已知山洞里面是由许多房间组成的迷宫每个房间可以通往周围八个房间迷宫大小是一个N*N的正方形其中有一些蝙蝠堵路。现在从起始(1,1)的位置进入洞穴寻找宝藏已有一个宝箱如果可以找到宝藏输出YES否则输出NO。
输入描述 第一行是一个正整数N2N ≤10,后面包含N*N行由012组成的矩阵其中0表示可以走1表示蝙蝠2表示宝藏的位置。 注意第一个房间没有蝙蝠
输出描述 一行找到宝藏输出YES否则输出NO 。
样例输入 1 6 0 0 1 1 0 0 1 0 0 1 0 0 0 0 0 1 2 0 0 1 1 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 样例输出 1 NO
样例输入 2 5 0 0 0 0 0 0 0 1 1 1 0 0 0 1 0 0 1 0 1 2 0 0 0 0 1 样例输出 2 YES
和迷宫的区别就是方向变多了
#include bits/stdc.h
using namespace std;
int n,ex,ey,a[25][25],vis[105][105];
bool flag;
bool check(int nx,int ny){return nx0nxnny0nynvis[nx][ny]0a[nx][ny]!1;
}
int dx[8]{0,1,1,1,0,-1,-1,-1};//右,右下,下,左下,左,上,右上
int dy[8]{1,1,0,-1,-1,-1,0,1};//右,右下,下,左下,左,上,右上
void dfs(int x,int y){if(xexyey){//cout x y;flag1;return;}for(int i0;i8;i){int nxxdx[i],nyydy[i];if(check(nx,ny)){vis[nx][ny]1;dfs(nx,ny);}}
}int main(){cinn;for(int i1;in;i){for(int j1;jn;j){cina[i][j];if(a[i][j]2) {exi;eyj;}}}vis[1][1]1;dfs(1,1);if(flag) coutYES;else coutNO;return 0;
}3089 探索迷宫
水题就不放题目了自己找吧
#include iostream
using namespace std;
int n,m,x1,y1;
bool flag;
int vis[25][25];
int dx[4] {1,0,-1,0},dy[4] {0,1,0,-1};
int mp[25][25];
void dfs(int x,int y)
{if(xx1 yy1){flag 1;return ;}for(int i0;i4;i){int nx xdx[i];int ny ydy[i];if(nx0nxnny0nymmp[nx][ny]!1vis[nx][ny]0){vis[nx][ny] 1;dfs(nx,ny);}}}
int main() {cinnm;for(int i1;in;i){for(int j1;jm;j){cinmp[i][j];}}if(mp[1][1]1){coutNO;return 0;}cinx1y1;vis[1][1] 1;dfs(1,1);if(flag) coutYES;else coutNO;return 0;
}3090 走迷宫
衍生版本就是开始与结束位置也是自己输入的
#includebits/stdc.h
using namespace std;
bool vis[105][105],f0;
int n,x,y,startx,starty;
char c[105][105];
int dx[4] {1,0,-1,0},dy[4] {0,1,0,-1};
void dfs(int x1,int y1)
{if(x1x y1y){f 1;}for(int i0;i4;i){int nx x1dx[i];int ny y1dy[i];if(nx0 nxn ny0 nyn vis[nx][ny]0 c[nx][ny].){vis[nx][ny] 1;dfs(nx,ny);}}
}
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cinn;for(int i0;in;i){for(int j0;jn;j){cinc[i][j];}}cinstartxstartyxy;if(c[startx][starty]# or c[x][y]#){coutno;return 0;}else{dfs(startx,starty);}if(f1) coutyes;else coutno;return 0;
}
2936 八个方向
水题只有方向变多了大家注意这个方向的数组一定要正确【此题copy杨同学的代码】
#include bits/stdc.h
using namespace std;
int n,ex,ey,a[25][25],vis[105][105];
bool flag;
bool check(int x,int y){return x1xny1yn!vis[x][y]a[x][y]!1;
}
int dx[8]{-1,0,1,1,1,0,-1,-1},dy[8]{1,1,1,0,-1,-1,-1,0};
void dfs(int x,int y){if(xexyey){flag1;return;}for(int i0;i8;i){int nxxdx[i],nyydy[i];if(check(nx,ny)){vis[nx][ny]1;dfs(nx,ny);}}
}int main(){cinn;for(int i1;in;i){for(int j1;jn;j){cina[i][j];if(a[i][j]2){exi;eyj;}}}if(a[1][1]1){coutNO;return 0;}vis[1][1]1;dfs(1,1);if(flag) coutYES;else coutNO;return 0;
}4143 中国象棋的马
做完八个方向来看看这个八个方向的衍生版本 不懂就看上图再不懂就微信私聊吧啥也别说了
#include bits/stdc.h
using namespace std;
int n,m,ex,ey,a[25][25],vis[105][105];
bool flag;
bool check(int x,int y){return x1xny1ym!vis[x][y]a[x][y]!1;
}
int dx[8]{-1,-2,-2,-1,1,2,2,1},dy[8]{2,1,-1,-2,-2,-1,1,2};
void dfs(int x,int y){if(xexyey){flag1;return;}for(int i0;i8;i){int nxxdx[i],nyydy[i];if(check(nx,ny)){vis[nx][ny]1;dfs(nx,ny);}}
}int main(){cinnm;for(int i1;in;i){for(int j1;jm;j){cina[i][j];}}cinexey;if(a[1][1]1){coutNO;return 0;}vis[1][1]1;dfs(1,1);if(flag) coutYES;else coutNO;return 0;
}说完这一类的题目我们接下来看看统计线路相关的题目
2937 八个方向统计线路
已知山洞里面是由许多房间组成的迷宫每个房间可以通往周围八个房间迷宫大小是一个N*N的正方形其中有一些蝙蝠堵路。现在从起始(1,1)的位置进入洞穴寻找宝藏只有一个宝箱统计有多少条线路可以找到宝藏。
输入描述 第一行是一个正整数N2N6,后面包含N*N行由012组成的矩阵其中0表示可以走1表示蝙蝠2表示宝藏的位置。
输出描述 一行一个整数表示可以找到宝藏的线路。
样例输入 1 6 0 0 1 1 0 0 1 0 0 1 0 0 0 0 0 1 2 0 0 1 1 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 样例输出 1 0
样例输入 2 2 0 0 0 2 样例输出 2 5
思路分析这个题目不是找一次终点而是多次找终点所以被归为一类的题目 这个题目的核心代码是 vis[nx][ny]1;dfs(nx,ny);vis[nx][ny]0;就是我们标记当前位置搜索完毕后要把当前位置给去除标记再次搜索看看有没有别的可能到达终点 代码如下【来自杨同学后续不说明了哈】
// 来自杨同学我就不写了后面大抵都是他的代码他把判断内容用check函数封装了
#include bits/stdc.h
using namespace std;
int n,ex,ey,a[105][105],vis[105][105],sum;
bool check(int x,int y){return x1xny1yn!vis[x][y]a[x][y]!1;
}
int dx[8]{-1,0,1,1,1,0,-1,-1},dy[8]{1,1,1,0,-1,-1,-1,0};
void dfs(int x,int y){if(xexyey){sum;return;}for(int i0;i8;i){int nxxdx[i],nyydy[i];if(check(nx,ny)){vis[nx][ny]1;dfs(nx,ny);vis[nx][ny]0;}}
}
int main(){cinn;for(int i1;in;i){for(int j1;jn;j){cina[i][j];if(a[i][j]2){exi;eyj;}}}if(a[1][1]1){cout0;return 0;}vis[1][1]1;dfs(1,1);coutsum;return 0;
}2935 统计线路
水
//这个风格是邢同学的
#includebits/stdc.h
using namespace std;
int vis[11][11],ans,n;
int mp[11][11];
int dx[4] {1,0,-1,0};
int dy[4] {0,1,0,-1};
void dfs(int x,int y)
{if(mp[x][y]2){ans;return ;} for(int i0;i4;i){int nx xdx[i];int ny ydy[i];if(nx0nxnny0nynvis[nx][ny]0mp[nx][ny]!1){vis[nx][ny] 1;dfs(nx,ny);vis[nx][ny] 0;}}
}
int main()
{cinn;for(int i1;in;i){for(int j1;jn;j){cinmp[i][j];}}vis[1][1] 1;dfs(1,1);coutans;return 0;
}
1353 围成面积 **
这个题就好玩了 编程计算由数字1围成的下列图形的面积。面积计算方法是统计数字1所围成的闭合曲线中点的数目。如下图所示在10 * 10的二维数组中有数字1围住了15个点因此面积为15。 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1 0 1 0 0 1 0 1 0 1 0 0 1 0 0 1 0 0 1 1 0 1 1 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0
输入描述 输入一个包含 0 和 1 数字的 10∗10 矩阵 输出描述 输出面积
样例输入 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1 0 1 0 0 1 0 1 0 1 0 0 1 0 0 1 0 0 1 1 0 1 1 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 样例输出 1 15
分析一下这个题要看1围起来的0的个数我们要把这个题的数据分三部分外层0中层1内层0一共是10行10列除去外层能搜索到的0的个数输入时判断累加的1的个数不就是中间的0的个数 上图 不理解的直接来找我
#include bits/stdc.h
using namespace std;
int dx[4]{0,1,0,-1},dy[4]{1,0,-1,0};
int a[105][105],sum1,sum2,ans;
bool flag;
bool check(int x,int y){return x1x10y1y10a[x][y]!1;
}
void dfs(int x,int y){a[x][y]1;for(int i0;i3;i){int nxxdx[i],nyydy[i];if(check(nx,ny)){sum2;dfs(nx,ny);}}
}
int main(){for(int i1;i10;i){for(int j1;j10;j){cina[i][j];if(a[i][j]1) sum1;}}for(int i1;i10;i){for(int j1;j10;j){if(a[i][j]0){sum2;dfs(i,j);flag1;break;}}if(flag) break;}ans100-sum1-sum2;coutans;return 0;
}6604 地图找车
水
#include bits/stdc.h
using namespace std;
char a[105][105];
int n,m,ex,ey,vis[105][105];
bool flag;
bool check(int x,int y){return x1xny1ym!vis[x][y]a[x][y]!X;
}
int dx[4]{0,1,0,-1},dy[4]{1,0,-1,0};
void dfs(int x,int y){if(xexyey){flag1;return;}for(int i0;i4;i){int nxxdx[i],nyydy[i];if(check(nx,ny)){vis[nx][ny]1;dfs(nx,ny);}}
}int main(){cinnm;for(int i1;in;i){for(int j1;jm;j){cina[i][j];if(a[i][j]*){exi;eyj;}}}if(a[1][1]X){coutNO;return 0;}vis[1][1]1;dfs(1,1);if(flag) coutYES;else coutNO;return 0;
}2929 寻宝
侠盗 Hank 经过千难万险终于来到了恶人岛为了拿到恶人岛的宝座去帮助穷人Hank 先对恶人岛进行了侦查发现恶人岛有一个迷阵宝藏摆在了迷阵的深处。迷阵由 M×N 个方 格组成有的方格内有可以发现 Hank 的守卫而有的方格内则是安全。为了展现自己的实 力Hank 决定不仅要拿走恶人岛的宝藏还要给他们留一封信告诉恶人自己有 g 种方法 找到宝藏。现在要求你来帮助他实现这个目标。 迷阵越大守卫越多。
输入描述
输入有一组测试数据以两个非零整数 N 和 M 开始两者均不大于20。N表示迷阵行数, M表示迷阵列数。接下来有 N 行, 每行包含 M 个字符,不同字符分别代表不同含义:
‘’Hank 所在的位置 ‘.’可以安全通行的方格 ‘#’有守卫的方格 ‘*’宝藏所在位置。 输出描述
一个整数 g,表示 Hank 有 g 种方法可以找到宝藏。如果他不可能找到宝藏, 则输出-1。
样例输入 1
8 8 .##…# #…#.# #.#.##… …#.###. #.#…#. …###.#. …#.*… .#…### 样例输出 1
4 样例输入 2
9 6 .#…#. .#.*.# .####. …#… …#… …#… …#… #..## .#…#. 样例输出 2
-1
思路水题就是多个判断
#include bits/stdc.h
using namespace std;
char a[105][105];
int n,m,fx,fy,ex,ey,vis[105][105],sum;
bool flag;
bool check(int x,int y){return x1xny1ym!vis[x][y]a[x][y]!#;
}
int dx[4]{0,1,0,-1},dy[4]{1,0,-1,0};
void dfs(int x,int y){if(xexyey){flag1;sum;return;}for(int i0;i4;i){int nxxdx[i],nyydy[i];if(check(nx,ny)){vis[nx][ny]1;dfs(nx,ny);vis[nx][ny]0;}}
}
int main(){cinnm;for(int i1;in;i){for(int j1;jm;j){cina[i][j];if(a[i][j]){fxi;fyj;}if(a[i][j]*){exi;eyj;}}}vis[fx][fy]1;dfs(fx,fy);if(!flag) cout-1;else coutsum;return 0;
}1791 多少块水洼
有一块 N×M 的土地雨后积起了水有水标记为‘W’干燥为‘.’。八连通的积水被认为是连接在一起的。请求出院子里共有多少水洼
输入描述
第一行为 N,M (1≤N,M≤100)。 下面为 N×M的土地示意图。
输出描述
一行共有的水洼数。
样例输入 1
10 12 W…WW. .WWW…WWW …WW…WW. …WW. …W… …W…W… .W.W…WW. W.W.W…W. .W.W…W. …W…W. 样例输出 1
3
思路:从每个点搜索并且标记如果搜索停止就看下个点搜索的情况。看最后能搜索到几个区域记得计数
#includebits/stdc.h
using namespace std;
int vis[105][105];
char mp[105][105];
int n,m,ans;
int dx[8] {0,1,1,1,0,-1,-1,-1};
int dy[8] {1,1,0,-1,-1,-1,0,1};
void dfs(int x,int y)
{for(int i0;i8;i){int nx xdx[i];int ny ydy[i];if(nx0 nxn ny0 nym mp[nx][ny]W vis[nx][ny]0){vis[nx][ny] 1;dfs(nx,ny);}}
}
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cinnm;for(int i0;in;i){for(int j0;jm;j){cinmp[i][j];}}for(int i0;in;i){for(int j0;jm;j){if(mp[i][j]W vis[i][j]0){ans;vis[i][j] 1;dfs(i,j);}}}coutans;return 0;
}
1852 连通块
一个 n×m 的方格图一些格子被涂成了黑色在方格图中被标为 1白色格子标为 0。问有多少个四连通的黑色格子连通块。四连通的黑色格子连通块指的是一片由黑色格子组成的区域其中的每个黑色格子能通过四连通的走法上下左右只走黑色格子到达该连通块中的其它黑色格子。
输入描述
第一行两个整数 n,m表示一个 n×m 的方格图。 接下来 n 行每行 m 个整数分别为 0 或 1表示这个格子是黑色还是白色。
输出描述
一行一个整数 ans表示图中有 ans 个黑色格子连通块。
样例输入 1
3 3 1 1 1 0 1 0 1 0 1 样例输出 1
3 提示
数据范围与提示 1≤n,m≤100
#include bits/stdc.h
using namespace std;
int dx[4]{-1,1,0,0},dy[4]{0,0,-1,1};
int n,m,a[105][105],sum;
bool check(int x,int y){return x1xny1yma[x][y]!0;
}
void dfs(int x,int y){a[x][y]0;for(int i0;i3;i){int nxxdx[i],nyydy[i];if(check(nx,ny)){dfs(nx,ny);}}
}
int main(){cinnm;for(int i1;in;i){for(int j1;jm;j){cina[i][j];}}for(int i1;in;i){for(int j1;jm;j){if(a[i][j]!0){sum;dfs(i,j);}}}coutsum;return 0;
}6611 吃蛋糕
小童今天跟家人一起吃生日蛋糕庆祝生日这块蛋糕是由n×m 的网格构成每个网格上面都放有不同的水果。小童把这些水果分为两类一类是自己喜欢吃的水果用’#‘来表示一类是自己不喜欢吃的水果用’.来表示。小童能吃到几块只包含自己喜欢吃的水果一块蛋糕为上下左右为#的连通区域。
输入描述
第一行为两整数 n,m 表示矩阵的大小为n×m0m,n≤100。 从第二行开始是一个 n×m 的矩阵。
输出描述
一行表示蛋糕块数
样例输入 1
4 5 .#.#. .#.## .##… #… 样例输出 1
3
#includebits/stdc.h
using namespace std;
int n,m;
int dx[4] {1,-1,0,0};
int dy[4] {0,0,1,-1};
int ans;
bool vis[105][105];
char g[105][105];
void dfs(int x,int y){for(int i0;i4;i){int nx xdx[i];int ny ydy[i];if(nx0 nxn ny0 nym g[nx][ny]# vis[nx][ny]0){vis[nx][ny] 1;dfs(nx,ny);}}
}
int main(){cinnm;for(int i1;in;i){for(int j1;jm;j){cing[i][j];}}for(int i1;in;i){for(int j1;jm;j){if(g[i][j]# vis[i][j]0){ans;vis[i][j] 1;dfs(i,j);}}}coutans;return 0;
}6624 数地图连通块面积
#includebits/stdc.h
using namespace std;
int n,m;
bool f;
int dx[4] {1,0,-1,0};
int dy[4] {0,1,0,-1};
int ans;
bool vis[105][105];
char g[105][105];
void dfs(int x,int y){for(int i0;i4;i){int nx xdx[i];int ny ydy[i];if(nx0 nxn ny0 nym g[nx][ny]# vis[nx][ny]0){vis[nx][ny] 1;ans;dfs(nx,ny);}}
}
int main(){cinnm;for(int i1;in;i){for(int j1;jm;j){cing[i][j];}}for(int i1;in;i){for(int j1;jm;j){if(g[i][j]# vis[i][j]0){vis[i][j] 1;dfs(i,j);coutans1 ;ans 0;f 1;}}}if(f0){cout-1;}return 0;
}6822 红与黑
第一行是两个整数 n 和 m表示房间是 n 行 m 列大小。在接下来的 n 行中每行包括 m 个字符。每个字符表示一块瓷砖的颜色规则如下:
‘.’黑色的瓷砖 ‘#’红色的瓷砖 ‘’黑色的瓷砖并且你站在这块瓷砖上。该字符在数据中出现一次。 输出描述
一行显示你从初始位置出发能到达的瓷砖数(注意记数时包括初始位置的瓷砖)。
样例输入 1
5 6 …#. …# … #…# .#…#. 样例输出 1
21 提示
数据范围与提示 1n,m20 注意此题中初始位置就是一个黑色区域要计数
#include bits/stdc.h
using namespace std;
char a[105][105];
int dx[4]{0,1,0,-1},dy[4]{1,0,-1,0};
int n,m,sum;
bool check(int x,int y){return x1xny1yma[x][y]!#;
}
void dfs(int x,int y){a[x][y]#;for(int i0;i3;i){int nxxdx[i],nyydy[i];if(check(nx,ny)){sum;dfs(nx,ny);}}
}
int main(){cinnm;for(int i1;in;i){for(int j1;jm;j){cina[i][j];}}for(int i1;in;i){for(int j1;jm;j){if(a[i][j]){sum;dfs(i,j);break;}}}coutsum;return 0;
}
