望江县城乡建设局网站,展示型网站制作服务,网站 建设 开发 协议,wordpress 菜单保存在哪#x1f483;#x1f3fc; 本人简介#xff1a;男 #x1f476;#x1f3fc; 年龄#xff1a;18 #x1f91e; 作者#xff1a;那就叫我亮亮叭 #x1f4d5; 专栏#xff1a;关于C/C那点破事 文章目录0.0 写在前面1. 中国象棋1.1 题干信息① 背景说明概述② 问题描述… 本人简介男 年龄18 作者那就叫我亮亮叭 专栏关于C/C那点破事 文章目录0.0 写在前面1. 中国象棋1.1 题干信息① 背景说明概述② 问题描述③ 输入格式④ 输出格式⑤ 样例输入⑥ 样例输出1.2 思路解释1.3 code展示2. 踏青2.1 题干信息① 背景说明概述② 问题描述③ 输入格式④ 输出格式⑤ 样例输入⑥ 样例输出2.2 思路解释2.3 code展示3. 迷宫解的方案数3.1 题干信息① 背景说明概述② 问题描述③ 输入格式④ 输出格式⑤ 样例输入⑥ 样例输出3.2 思路解释3.3 code展示4. 最大的蛋糕块4.1 题干信息① 背景说明概述② 问题描述③ 输入格式④ 输出格式⑤ 样例输入⑥ 样例输出4.2 思路解释4.3 code展示5. 家谱5.1 题干信息① 背景说明概述② 问题描述③ 输入格式④ 输出格式⑤ 样例输入⑥ 样例输出5.2 思路解释5.3 code展示最后感谢大家支持u ^ _ ^0.0 写在前面 书接上文上次我们讲到了深搜的思想与经典的迷宫问题这次我们不再细节性讲解其思想重在针通过几道例题来实践掌握深搜的用法欢迎大佬们来指点一二我们一起加油还没了解的可以直接点进行学习哦【C算法】dfs深度优先搜索(上) ——【全面深度剖析经典例题展示】 1. 中国象棋
1.1 题干信息
① 背景说明概述 中国象棋博大精深其中马的规则最为复杂也是最难操控的一颗棋子。我们都知道象棋中马走日比如在(2, 4)位置的一个马【如下图所示】跳一步能到达的位置有(0,3)(0,5)(1,2)(1,6)(3,2)(3,6)(4,3)(4,5)。 注意上图中竖直向下的是x水平向右的是y
② 问题描述 蒜头君正在和花椰妹下棋蒜头君正在进行战略布局他需要把在(x, y)位置的马跳到(x’, y’)位置以达到威慑的目的。但是棋盘大小有限制棋盘是一个10 x 9的网格左上角坐标为(0,0)右下角坐标为(9, 8)马不能走出棋盘并且有些地方已经有了棋子马也不能跳到有棋子的点。蒜头君想知道在不移动其他棋子的情况下能否完成他的战略目标。 ③ 输入格式
输入一共10行每行一个长度为9的字符串。输入表示这个棋盘我们用.表示空位置用#表示该位置有棋子用S表示初始的马的位置用T表示马需要跳到的位置。输入保证一定只有一个S和T。
④ 输出格式
如果在不移动其他棋子的情况下马能从S跳到T那么输出一行Yes否则输出一行No。
⑤ 样例输入
.#....#S#
..#.#.#..
..##.#..#
......##.
...T.....
...#.#...
...#.....
...###...
.........
.##......⑥ 样例输出
Yes
1.2 思路解释 和上一篇例题的思路基本一模一样只不过上次迷宫只能是上下左右走而这次的象棋中可以走八个方向只是对x、y坐标的改变不同而已其他基本一致所以这里就不过多赘述了不太明白的可以点这里哦【C算法】dfs深度优先搜索(上) ——【全面深度剖析经典例题展示】 大致思路如下
①判断象棋终点记录所走路径②完善搜索回溯处理数组边界③找寻马儿起点打印结束路径
1.3 code展示
#includeiostream
#includestdio.h
using namespace std;int n, m;
char pos[105][105];
int trace[105][105];
int dir[8][2] { {-1 , -2} , {-2 , -1} , {-2 , 1} , {-1 , 2} , {1 , 2} , {2 , 1} , {2 , -1} , {1 , -2} }; // 找出马儿走日时x、y坐标变化的所有情况【基本按逆时针来】bool check_in(int x, int y) { // 判断数组是否越界return (x 1 x n y 1 y m); //这里表示的是如果()里为真则返回true否则返回false
}bool dfs(int x, int y) {if (pos[x][y] T) {return true;}pos[x][y] x; //用x记录路径trace[x][y] 1; //标记已走过for (int i 0; i 8; i) {int xx x dir[i][0]; //表示x加上第几个方向的第1个数即变化后行的坐标int yy y dir[i][1]; //表示y加上第几个方向的第2个数即变化后列的坐标if (pos[xx][yy] ! # check_in(xx, yy) !trace[xx][yy]) {if (dfs(xx , yy)) {return true;} }} pos[x][y] .; // 如果一个位置的上下左右都走不了则取消该位置的路径进行回溯回溯过程把之前已标记的x改回.trace[x][y] 0; //走不通则回溯过程标记为没走过return false;
}int main() {cin n m;//输入象棋地图 找儿的起点int x , y;for (int i 1; i n; i) {for (int j 1; j m; j) {cin pos[i][j];if (pos[i][j] S) {x i, y j;}}}cout -------------------------------- endl;if (dfs(x , y)) {cout Yes!!! endl;for (int i 1; i n; i) {for (int j 1; j m; j) {cout pos[i][j];} cout endl;}}else {cout No!!! endl;}return 0;
}2. 踏青
2.1 题干信息
① 背景说明概述 蒜头君和他的朋友周末相约去召唤师峡谷踏青。他们发现召唤师峡谷的地图是由一块一块格子组成的有的格子上是草丛有的是空地。草丛通过上下左右4个方向扩展其他草丛形成一片草地任何一片草地中的格子都是草丛并且所有格子之间都能通过上下左右连通。如果用#代表草丛. 代表空地则下面的峡谷中有2片草地。 ##..
..##② 问题描述
处在同一个草地的2个人可以相互看到空地看不到草地里面的人。他们发现有一个朋友不见了现在需要分头去找每个人负责一片草地蒜头君想知道他们至少需要多少人。
③ 输入格式
第一行输入n,m(1 ≤ n, m 100) 表示峡谷大小。接下来输入n行字符串表示峡谷的地形。
④ 输出格式
输出至少需要多少人。
⑤ 样例输入
5 6
.#....
..#...
..#..#
...##.
.#....⑥ 样例输出
5
2.2 思路解释
根据题意最后要求最少人数而根据一人负责一片草地则就转换求最少草地数就是该地形最少有多少片土地。我们先输入地形再依次遍历每个格子是否为草地如果不是草地直接略过如果是草地则是否之前找过如果找过则还是略过如果没找过则先记录下已找过结果1并对该草地的上下左右遍历是否是未被找的草地【深搜思想】。最后输出结果。
2.3 code展示
#includeiostream
#includestdio.h
using namespace std;int n, m, ans 0;
char pos[105][105];
bool trace[105][105];//法一
//bool check_in(int x, int y) {
// return (x 1 x n y 1 y m);
//}
//
//void dfs(int x, int y) {
// if (check_in(x, y) pos[x][y] # !trace[x][y]) {
// trace[x][y] 1;
// dfs(x, y 1);
// dfs(x 1, y);
// dfs(x, y - 1);
// dfs(x - 1, y);
// }
//}//法二
void dfs(int x, int y) {if (x 1 || x n || y 1 || y m || trace[x][y] || pos[x][y] .) {return;}trace[x][y] true;dfs(x - 1, y); //记录上面dfs(x , y - 1); //记录左面dfs(x 1, y); // 记录下面dfs(x , y 1); //记录右面
}int main() {cin n m;for (int i 1; i n; i) {for (int j 1; j m; j) {cin pos[i][j];}}for (int i 1; i n; i) {for (int j 1; j m; j) {if (!trace[i][j] pos[i][j] #) { // 假如是草丛的话且之前没找过dfs(i, j); // 把这个位置和周边草丛标记好ans; //记录草丛数量}}}cout ans endl;return 0;
}3. 迷宫解的方案数
3.1 题干信息
① 背景说明概述 蒜头君是一个玩迷宫的高手天下还没有能难住他的迷宫。但是总有人喜欢习难蒜头君不停的给蒜头君出难题。这个出题的人很聪明他知道天下还没有能难住蒜头君的迷宫。 ② 问题描述
所以他便转换思维问蒜头君在不走重复路径的情况下总共有多少不同可以到达终点的路径呢?蒜头君稍加思索便给出了答案你要不要也来挑战一下?
③ 输入格式
第一行输入两个整数n(1≤n≤11), m(1≤m≤11), 表示迷宫的行和列。然后有一个n*m的地图地图由.、#、 s 、e 这四个部分组成。.表示可以通行的路# 表示迷宫的墙s 表示起始点e 表示终点。
④ 输出格式
输出一个整数表示从s到达e的所有方案数。
⑤ 样例输入
5 5
s####
.####
.####
.####
....e⑥ 样例输出
1
3.2 思路解释
本题和前面迷宫例题思路差不多但这个题是要统计到终点的路线的个数所以如果能到终点则需要ans如果该节点的上下左右都行不通则在四周判断完后需要清空路径trace[x][y]0来继续探索下一条路。
3.3 code展示
#includeiostream
#includestdio.h
using namespace std;int n, m, ans 0;
char pos[105][105];
bool trace[105][105];
int dir[4][2] { {-1, 0},{0,-1},{1,0},{0,1} };bool check_in(int x, int y) {return (x 1 x n y 1 y m);
}void dfs(int x, int y) {if (pos[x][y] e) {ans; //节点为终点所以找到一条走到终点的路ansreturn ;}if (check_in(x, y) pos[x][y] ! # !trace[x][y]) { //如果这个节点不是终点且没越界不是墙且没走过则统计四周情况trace[x][y] 1;for (int i 0; i 4; i) {int xx x dir[i][0];int yy y dir[i][1];dfs(xx, yy);}trace[x][y] 0; //清空路线找下一条路}
}int main() {cin n m;int x, y;for (int i 1; i n; i) {for (int j 1; j m; j) {cin pos[i][j];if (pos[i][j] s) {x i, y j;}}}dfs(x, y);cout ans endl;return 0;
}4. 最大的蛋糕块
4.1 题干信息
① 背景说明概述 这一天蒜头君生日他的朋友们一起来给蒜头君买一个大的蛋糕过生日。游戏做完后到了切蛋糕的时刻了朋友们知道蒜头君喜欢吃蛋糕便让蒜头君自己给自己切-块最大的。蒜头君看朋友们这么热情也就不客气了。 ② 问题描述
这块蛋糕是由R*C的网格构成每个网格上面都放有不同的水果。蒜头君把这些水果分为两类一类是自己喜欢吃的水果用#来表示;一类是自己不喜欢吃的水果用.来表示。蒜头君对切出的蛋糕有如下要求: 切出的蛋糕连成一块(可以不为矩形但必须在网格上连通)切出的蛋糕只包含自己喜欢吃的水果 请问蒜头君最大可以吃到多大的蛋糕?
③ 输入格式
第一行输入两个被空格隔开的整数R(1≤R≤1000)和C(1≤C≤1000)。然后会有一个R*C的网格由#和.组成。
④ 输出格式
输出一个整数表示蒜头君可以吃到的蛋糕最大是多少(即对应到网格中的格子数)。
⑤ 样例输入
5 6
.#....
..#...
..#..#
...##.
.#....⑥ 样例输出
2
4.2 思路解释
和题2《踏青》的总体思路一样但《踏青》求的是带#每部分的数量而本题是求每部分里#最多的数量。所以这道题只需要在统计每部分时记录#的数量再进行比较即可。
4.3 code展示
#includeiostream
#includestdio.h
using namespace std;int r, c, ans 0, cnt 0;
char pos[105][105];
bool trace[105][105];
int dir[4][2] { {-1, 0},{0,-1},{1,0},{0,1} };bool check_in(int x, int y) {return (x 1 x r y 1 y c);
}void dfs(int x, int y) {if (!check_in(x, y) || pos[x][y] ! # || trace[x][y]) { //深搜过程中不合要求的返回;return;}trace[x][y] 1; //标记访问过cnt; //记录数量for (int i 0; i r; i) {int xx x dir[i][0];int yy y dir[i][1];if (pos[xx][yy] #) {dfs(xx, yy);}}
}int main() {cin r c;int x, y;for (int i 1; i r; i) {for (int j 1; j c; j) {cin pos[i][j];}}for (int i 1; i r; i) {for (int j 1; j c; j) {if (!trace[i][j] pos[i][j] #) { //如果是#且之前没被访问过则用dfs记录下cnt 0; //需要将该位置能求到的数量重置为0dfs(i, j); //用dfs求一下所有‘#’的数量if (ans cnt) {ans cnt; //更新一下ans}}}}cout ans endl;return 0;
}5. 家谱
5.1 题干信息
① 背景说明概述 家谱又称族谱、宗谱等是一种以表谱形式记载一个家族的世系繁衍及重要人物事迹的书。皇帝的家谱称玉牒如新朝玉牒、皇宋玉牒。它以记载父系家族世系、人物为中心由正史中的帝王本纪及王侯列传、年表等演变而来。家谱是一种特殊的文献就其内容而言是中国五千年文明史中具有平民特色的文献记载的是同宗共祖血缘集团世系人物和事迹等方面情况的历史图籍。家谱属珍贵的人文资料对于历史学、民俗学、人口学、社会学和经济学的深入研究均有其不可替代的独特功能。 ② 问题描述
这一天蒜头君拿到了自己家的家谱蒜头君便想知道在自己家的家谱中每位祖先有多少直系后代(直系后代包括他的孩子和他孩子的直系后代)。但是家族历史源远流长家谱实在太庞大了自己一个人完全数不过来。热心的你便自告奋勇帮蒜头君写一个程序来统计每位祖先有多少直系后代。
③ 输入格式
输入的第一行有一个整数n(1n≤100000)表示家谱中的总人数。接下来读入n- 1行每行有两个整数x(1≤x≤n),y(1≤y≤n),表示x是y的父母。
④ 输出格式
输出n行每行有一个整数表示第i个人有多少个直系后代。
⑤ 样例输入
4
1 2
1 3
2 4⑥ 样例输出
3 1 0 0
5.2 思路解释
本题输入数值的大小不确定所以如果指定数组大小则可能报错所以我们采用动态数组vector来统计son数量。所以首先我们先找根节点所以要找直系儿子则需要把所有儿子的后代标记一下最后未被标记的就是直系儿子。我们找到根节点需要先对根节点的后代进行搜索直到找到答案。
5.3 code展示
#includeiostream
#includestdio.h
#includevector
using namespace std;
const int N 1e5 10;int n, x, y, u;
vectorint son[N]; //使用动态数组便于插入和删除
bool judge_son[N]; //判断是否是儿子
int ans[N];int dfs(int a) { // 找有多少个直系后代【不包括自己】但统计时为了方便则统计自己int cnt 0;int len son[a].size();for (int i 0; i len; i) { //首先找根节点的后代cnt dfs(son[a].at(i)); //找根节点的直接后代或者写dfs(son[u][i])}ans[u] cnt; //统计后代个数return cnt 1; //加上自己
}int main() {cin n;for (int i 1; i n; i) {cin x y; //输入x,y 表示x是y的父亲son[x].push_back(y); //将y放入son[x]的动态数组中judge_son[y] true; //y已经作为儿子了所以标为true;}for (int i 1; i n; i) { //找起始位置即找“根”节点if (!judge_son[i]) { //找到赋给u,并breaku i;break;}}dfs(u);for (int i 1; i n; i) {cout ans[i] endl;}return 0;
}最后感谢大家支持u ^ _ ^ 如果感觉这篇文章对你有帮助的话不妨三连支持下十分感谢(✪ω✪)。 printf(点个赞吧*^*);cout 收藏一下叭o_o;System.out.println(评论一下吧^_^);print(关注一下叭0-0)
