文章目录
前言
一、DFS
二、例题，代码
AcWing 1112. 迷宫
本题分析
AC代码
DFS
BFS
AcWing 1113. 红与黑
本题分析
AC代码
DFS
BFS
三、时间复杂度
前言
复习acwing算法提高课的内容，本篇为讲解算法：DFS之连通性模型，关于时间复杂度：目前博主不太会计算，先鸽了，日后一定补上。
一、DFS
深度优先搜索，基础的模板我们已经讲过，见：DFS，在这里不做过多赘述，本文主要针对一些dfs的类型题目做相应的讲解
二、例题，代码
AcWing 1112. 迷宫
本题链接：AcWing 1112. 迷宫
本博客提供本题截图：
本题分析
dfs的板子题，注意题目中的坑：A，B不一定是两个不同的点，起点和终点也可能是'#'
AC代码
DFS
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int N = 110; int k, n, la, ha, lb, hb; char g[N][N]; bool st[N][N]; bool dfs(int x, int y) { if (g[x][y] == '#') return false; if (x == hb && y == lb) return true; int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -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 >= n) continue; if (st[a][b]) continue; if (dfs(a, b)) return true; } return false; } int main() { scanf("%d", &k); while (k -- ) { scanf("%d", &n); for (int i = 0; i < n; i ++ ) scanf("%s", g[i]); scanf("%d%d%d%d", &ha, &la, &hb, &lb); memset(st, false, sizeof st); if (dfs(ha, la)) puts("YES"); else puts("NO"); } return 0; }
BFS
#include <cstdio> #include <cstring> #include <map> #define x first #define y second using namespace std; typedef pair<int, int> PII; const int N = 110, M = N * N; PII q[M]; char g[N][N]; bool st[N][N]; int k, n, ha, la, hb, lb; bool bfs() { if (g[ha][la] == '#') return false; if (la == lb && ha == hb) return true; int dx[4] = {0, -1, 0, 1}, dy[4] = {-1, 0, 1, 0}; int hh = 0, tt = 0; q[0] = {ha, la}; st[ha][la] = true; while (hh <= tt) { auto t = q[hh ++]; for (int i = 0; i < 4; i ++ ) { int a = t.x + dx[i], b = t.y + dy[i]; if (a < 0 || a >= n || b < 0 || b >= n) continue; if (st[a][b] || g[a][b] == '#') continue; if (a == hb && b == lb) return true; q[++ tt] = {a, b}; st[a][b] = true; } } return false; } int main() { scanf("%d", &k); while (k -- ) { scanf("%d", &n); for (int i = 0; i <n; i ++ ) scanf("%s", g[i]); scanf("%d%d%d%d", &ha, &la, &hb, &lb); memset(st, false, sizeof st); if (bfs()) puts("YES"); else puts("NO"); } return 0; }
AcWing 1113. 红与黑
本题链接：AcWing 1113. 红与黑
本博客提供本题截图：
本题分析
其实就是Flood Fill算法的dfs写法
AC代码
DFS
#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 25; int n, m; char g[N][N]; bool st[N][N]; int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}; 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 (st[a][b]) continue; if (g[a][b] == '#') continue; cnt += dfs(a, b); } return cnt; } int main() { while (cin >> m >> n, n || m) { memset(st, false, sizeof st); 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; break; } cout << dfs(x, y) << endl; } return 0; }
BFS
就是Flood Fill算法
三、时间复杂度
关于DFS之连通性模型的时间复杂度以及证明，后续会给出详细的说明以及证明过程，目前先鸽了。
