电子商务网站建设的论文,石家庄做网站网络公司,网络营销的渠道,wordpress 默认头像 本地算法提高课笔记 目录 迷宫题意思路代码 红与黑题意思路代码 DFS 的搜索分为两大部分#xff1a; 内部搜索#xff1a;一个图中从一个点搜到另一个点外部搜索#xff1a;从一张图#xff08;状态#xff09;搜到另一张图#xff08;状态#xff09;
在第一个部分里是图…算法提高课笔记 目录 迷宫题意思路代码 红与黑题意思路代码 DFS 的搜索分为两大部分 内部搜索一个图中从一个点搜到另一个点外部搜索从一张图状态搜到另一张图状态
在第一个部分里是图内部点的搜索每个点只能搜一次因此搜过的点不需要恢复到原来的还没被搜过的状态意思就是st数组不恢复
而第二个部分是点的集合之间的搜索每次搜索完一定要恢复到原有状态才可以进行下一步搜索意思就是st数组每次需要恢复原状
迷宫
原题链接
一天Extense在森林里探险的时候不小心走入了一个迷宫迷宫可以看成是由 n∗n 的格点组成每个格点只有2种状态.和#前者表示可以通行后者表示不能通行。
同时当Extense处在某个格点时他只能移动到东南西北(或者说上下左右)四个方向之一的相邻格点上Extense想要从点A走到点B问在不走出迷宫的情况下能不能办到。
如果起点或者终点有一个不能通行(为#)则看成无法办到。
注意A、B不一定是两个不同的点。
输入格式
第1行是测试数据的组数 k后面跟着 k 组输入。
每组测试数据的第1行是一个正整数 n表示迷宫的规模是 n∗n 的。
接下来是一个 n∗n 的矩阵矩阵中的元素为.或者#。
再接下来一行是 4 个整数 ha,la,hb,lb描述 A 处在第 ha 行, 第 la 列B 处在第 hb 行, 第 lb 列。
注意到 ha,la,hb,lb 全部是从 0 开始计数的。
输出格式
k行每行输出对应一个输入。
能办到则输出“YES”否则输出“NO”。
数据范围
1 ≤ n ≤ 100
输入样例
2
3
.##
..#
#..
0 0 2 2
5
.....
###.#
..#..
###..
...#.
0 0 4 0输出样例
YES
NO题意
给出一张图两个点问能不能从一个点走到另一个点
思路
直接bfs遍历看能不能从一个点遍历到另一个
代码
#include bits/stdc.husing namespace std;const int N 110;int n;
char g[N][N]; // 存图
int xa, ya, xb, yb; // 标记起点终点
int dx[4] {0, 0, 1, -1}, dy[4] {1, -1, 0, 0};
bool st[N][N]; // 判重bool dfs(int x, int y)
{if (g[x][y] #) return false;if (x xb y yb) return true;st[x][y] true;for (int i 0; i 4; i ) // 遍历四个操作{int a x dx[i], b y dy[i];if (a 0 || a n || b 0 || b n) continue; // 位置不合法if (st[a][b]) continue; // 已遍历if (dfs(a, b)) return true;} return false;
}int main()
{ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);int t;cin t;while (t -- ){cin n;for (int i 0; i n; i ) cin g[i];cin xa ya xb yb;memset(st, false, sizeof st);if (dfs(xa, ya)) cout YES\n;else cout NO\n;}
}红与黑
原题链接
有一间长方形的房子地上铺了红色、黑色两种颜色的正方形瓷砖。
你站在其中一块黑色的瓷砖上只能向相邻上下左右四个方向的黑色瓷砖移动。
请写一个程序计算你总共能够到达多少块黑色的瓷砖。
输入格式
输入包括多个数据集合。
每个数据集合的第一行是两个整数 W 和 H分别表示 x 方向和 y 方向瓷砖的数量。
在接下来的 H 行中每行包括 W 个字符。每个字符表示一块瓷砖的颜色规则如下
1‘.’黑色的瓷砖 2‘#’红色的瓷砖 3‘’黑色的瓷砖并且你站在这块瓷砖上。该字符在每个数据集合中唯一出现一次。
当在一行中读入的是两个零时表示输入结束。
输出格式
对每个数据集合分别输出一行显示你从初始位置出发能到达的瓷砖数(记数时包括初始位置的瓷砖)。
数据范围
1 ≤ W , H ≤ 20
输入样例
6 9
....#.
.....#
......
......
......
......
......
#...#
.#..#.
0 0输出样例
45题意
一个图分为红黑方块问某一个黑方块的连通块个数
思路
本质上是个Flood Fill问题可以用BFS实现
用DFS也是一样的只是搜索顺序不一样
代码
#include bits/stdc.husing namespace std;const int N 25;int n, m;
char g[N][N]; // 存图
bool st[N][N]; // 判重
int dx[4] {0, 0, -1, 1}, dy[4] {1, -1, 0, 0};int dfs(int x, int y)
{int cnt 1;st[x][y] true;for (int i 0; i 4; i ){int a x dx[i], b y dy[i];if (a 0 || a n || b 0 || b m) continue; // 位置不合法if (g[a][b] ! .) continue; // 不是黑色的if (st[a][b]) continue; // 已遍历cnt dfs(a, b);}return cnt;
}int main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);while (cin m n, n || m){for (int i 0; i n; i ) cin g[i];int x, y;for (int i 0; i n; i ) for (int j 0; j m; j )if (g[i][j] ) // 找起点{x i;y j;}memset(st, false, sizeof st);cout dfs(x, y) \n;}
}
