Homework Introduction
搜索
递归
- 一个实际问题的各种情况构成的集合通常称为 “状态空间” ， 而程序的运行则是对状态空间的遍历
- 算法和数据结构则通过划分、归纳、提取、抽象来帮助提高程序遍历状态空间的效率
- 递归就是其中一种遍历状态空间的基本方式
B3621 枚举元组
-
#include <bits/stdc++.h> using namespace std; const int N = 10; int ans[N]; int n, k; void dfs(int x) { if (x == n + 1) { for (int i = 1; i <= n; i++) cout << ans[i] << " "; cout << endl; return ; } // 遍历找其他的点,看能否填充 for (int i = 1; i <= k; i++) { ans[x] = i; dfs(x + 1); } } int main() { cin >> n >> k; dfs(1); return 0; }
B3622 枚举子集（递归实现指数型枚举）
-
先大概画出递归搜素树 考虑枚举顺序 在n 个位置上 填 N 或 Y N 和 Y 可以重复填， 不需要标记 -
#include <bits/stdc++.h> using namespace std; const int N = 15; char ans[N]; int n; // 在位置 X 上进行填充 void dfs(int x) { // 结束条件 if (x == n + 1) { for (int i = 1; i <= n; i++) { cout << ans[i]; } cout << endl; return ; } // 填充 for (int i = 1; i <= 2; i++) { if (i == 1) ans[x] = 'N'; if (i == 2) ans[x] = 'Y'; dfs(x + 1); // 填充下一个位置 } } int main() { cin >> n; dfs(1); return 0; }
P10448 组合型枚举
-
#include <bits/stdc++.h> using namespace std; const int N = 25; int ans[N]; int n, m; // last 记录上一次搜索的位置 // x当前要填充的位置 void dfs(int last, int x) { if (x == m + 1) { for (int i = 1; i <= m; i++) { printf("%d ", ans[i]); } printf("\n"); } // 可行性剪枝 // 剩下的数字 n - last 个 // 已经选择的数字有几个，(x-1) if (n - last + (x - 1) < m) return ; // 可行性剪枝 // 填充当前数字 for (int i = last + 1; i <= n; i++) { ans[x] = i; dfs(i, x + 1); } } int main() { cin >> n >> m; dfs(0, 1); return 0; }
B3623 枚举排列（递归实现排列型枚举）
-
// 1. 排列 // 2. n个人里面选择k个 -
#include <bits/stdc++.h> using namespace std; int n, k; int ans[15]; bool vis[15]; void dfs(int x) { if (x == k + 1) { for (int i = 1; i <= k; i++) cout << ans[i] << " "; cout << endl; return ; } for (int i = 1; i <= n; i++) { if (vis[i]) continue; vis[i] = 1; ans[x] = i; dfs(x + 1); vis[i] = 0; } } int main() { cin >> n >> k; dfs(1); return 0; }
深度优先搜索
- 按照深度优先的顺序对 “问题状态空间” 进行搜索的算法
- 使用深度优先搜索算法求解问题，就相当于在一张图上进行深度优先遍历
深搜是一类包括遍历形式、状态记录与检索、剪枝优化等算法整体设计的统称- 为了避免重复访问：我们对状态进行记录和检索
- 为了使程序更加高效，我们提前剪除搜索树上不可能是答案的子树和分支，不去进行遍历
P10483 小猫爬山
-
可以尝试依次把每一只小猫分配到一辆已经租用的缆车上 或者新租一辆缆车安置这只小猫 关系的状态：已经运送的小猫有多少只， 已经租用的缆车有多少量 每辆缆车上当前搭载的小猫重量之和 dfs(now,cnt) 处理第 now 只小猫的分配过程(前now-1已经处理了) 并且当前已经租用了cnt 辆车 搭载量，用一个全局数组 cab[] 来记录 优先搜索重量较大的小猫，减少搜索树“分支”的数量 当发现cnt 已经大于之前已经搜索出来的答案了，就直接退出，减枝 优先搜索重量较大的猫，减少搜索树 分支 -
#include <bits/stdc++.h> using namespace std; // cab[i] 第i辆车装载的重量 int c[20], cab[20], n, w, ans; void dfs(int now, int cnt) { if (cnt >= ans) return ; // 最优性剪枝 if (now == n + 1) { ans = min(ans, cnt); return ; } // 先分配已租用的缆车 for (int i = 1; i <= cnt; i++) { if (cab[i] + c[now] <= w) { cab[i] += c[now]; dfs(now + 1, cnt); cab[i] -= c[now]; // 回溯 } } // 新开一辆缆车 cab[cnt + 1] = c[now]; dfs(now + 1, cnt + 1); cab[cnt + 1] = 0; // 回溯 } int main() { cin >> n >> w; for (int i = 1; i <= n; i++) cin >> c[i]; sort(c + 1, c + 1 + n); reverse(c + 1, c + 1 + n); // 优先装载质量较大的，减少分枝 ans = n; dfs(1, 0); cout << ans; return 0; }
P10482 Sudoku 2
-
每一行出现1-9 每一列出现1-9 3*3的九宫格出现1-9 暴搜：搜索的顺序 1.每次随意挑选一个空白格子 2.枚举这个该格子选哪个数 3. DFS TLE 看 (x,y) 位置可以用哪些数 每一个位置不是 0 就是 1 如果是 1 代表这个数字可以用 row[i] : 存储一个二进制数 0 到 2^9-1 col[j] : 存储一个二进制数 0 到 2^9-1 cell[i][j] : 存储一个二进制数 0 到 2^9-1 可以选用的数字就是他们的交集 给 九宫格进行标号 (0,0) (0,1)(0,2) (1,0) row[x] & col[y] &cell[x/3][y/3] 最后 & 完的数字就是我们可以用的数字 lowbit(x) 返回数字 x 的最后一个 1 lowbit(10010) = 10 -
#include <bits/stdc++.h> using namespace std; const int N = 9; // 优化，ones 记录这个里面有几个 1 // mp 数组记录这个1 是第几个位置 int ones[1 << N], mp[1 << N]; int row[N], col[N], cell[3][3]; char str[100]; inline int lowbit(int x) { return x & -x; } void init() { for (int i = 0; i < N; i++) row[i] = col[i] = (1 << N) - 1; for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++) cell[i][j] = (1 << N) - 1; } inline int get(int x, int y) { return row[x] & col[y] & cell[x / 3][y / 3]; } bool dfs(int cnt) { if (!cnt) return 1; // 找出可选方案数最小的 int minn = 10; int x, y; for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) if (str[i * 9 + j] == '.') { int t = ones[get(i, j)]; if (t < minn) { minn = t; x = i, y = j; } } for (int i = get(x, y) ; i ; i -= lowbit(i)) { // 当前位置要填充的数字是 t int t = mp[lowbit(i)]; // 修改状态 row[x] -= 1 << t; col[y] -= 1 << t; cell[x / 3][y / 3] -= 1 << t; str[x * 9 + y] = '1' + t; if (dfs(cnt - 1)) return 1; // 回溯 row[x] += 1 << t; col[y] += 1 << t; cell[x / 3][y / 3] += 1 << t; str[x * 9 + y] = '.'; } return 0; } int main() { for (int i = 0; i < N; i++) mp[1 << i] = i; for (int i = 0; i < 1 << N ; i++) { int s = 0; for (int j = i ; j ; j -= lowbit(j)) s++; ones[i] = s; // i 的二进制表示中有 s 个1 } while (cin >> str, str[0] != 'e') { init(); int cnt = 0; for (int i = 0, k = 0; i < N ; i++) for (int j = 0; j < N; j++, k++) { if (str[k] != '.') { // 1 - 9 映射到下标 0 - 8 int t = str[k] - '1'; row[i] -= 1 << t; col[j] -= 1 << t; cell[i / 3][j / 3] -= 1 << t; } else cnt++; } dfs(cnt); cout << str << endl; } return 0; }
剪枝
- 剪枝：就是减小搜索树规模、尽早排除搜索树中不必要的分支的一种手段
优化搜索顺序
- 不同的搜索顺序会产生不同的搜索树的形态，其规模大小也相差甚远
- 例如小猫爬山中，把小猫按照重量递减的顺序进行搜索
- 例如数独中，优先搜索
能填的合法数字最少的位置
排除等效冗余
- 如果能够判定从搜索树的当前节点上沿着某几条不同分支到达的子树是等效的，那么只需要对其中的一条分支执行搜索
可行性剪枝
- 如果发现分支已经无法到达递归边界，就执行回溯
- 某些题目的限制范围是一个区间，可行性剪枝也被称为上下界剪枝
最优性剪枝
- 最优化搜索过程中，如果当前花费的代价已经超过了当前搜索到的最优解，剪枝，回溯
记忆化
- 记录每个状态的搜索结果，在重复遍历一个状态时直接检索并返回
P1120 小木棍
-
1. 优化搜索顺序，把木棍从大到小排序，优先尝试较长的木棍 2. 排除等效冗余 (1).限制先后加入一根原始木棍的长度是依次递减的，先拼上一根长度为x 的木棍，再拼上一根长度为y 的木棍，与先拼上y,然后再拼接x显然是等效的 只需要搜索其中一中 (2).对于当前木棍，记录最近一次尝试拼接的木棍长度 如果分支搜索失败回溯，不再尝试向该木棒中拼接其他相同长度的木棍(必定也会失败) (3).如果在当前原始木棒中“尝试拼入的第一根木棍”的递归分支就返回失败 那么直接判定当前分支失败，立即回溯 这是因为在拼入这根木棍前，面对的原始木棍都是空的(还没有进行拼接) 这些木棍是等效的，木棍拼在当前的木棒中失败，拼在其他木棒中也一样会失败 (4).如果在当前原始木棒中拼入一根木棍后，木棒恰好被拼接完整， 并且接下来的拼接剩余原始木棒的递归分支失败，那么直接判定当前分支失败，立即回溯 该剪枝可以贪心解释，再用一根木棍拼完当前原始木棒必然比再用若干 根木棍拼完当前原始木棍更好，这里当前只用一根木棍就拼接完剩下的 都不能搜索成功，用更多的木棍，也不可能会有更好的结果 -
#include <bits/stdc++.h> using namespace std; int a[100], v[100], n, len, cnt; // 正在拼第 stick 根原始木棍(已经拼接好了 stick-1根) // 第 stick 根原始木棍的当前长度为 cab // 拼接到第stick 根木棒中的上一根小木棍为 last bool dfs(int stick, int cab, int last) { // 所有原始木棍已经拼接好，搜索成功 if (stick > cnt) return 1; // 第 stick 根木棍已经拼好，去拼下一根 if (cab == len) return dfs(stick + 1, 0, 1); int fail = 0; // 剪枝2 // 剪枝1：小木棍长度递减(从last 开始枚举) for (int i = last ; i <= n; i++) { if (!v[i] && cab + a[i] <= len && fail != a[i]) { v[i] = 1; if (dfs(stick, cab + a[i], i + 1)) return 1; fail = a[i]; v[i] = 0; if (cab == 0 || cab + a[i] == len) return 0; // 剪枝 3 4 } } return 0; } int main() { while (cin >> n && n) { int sum = 0, val = 0; for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); sum += a[i] ; val = max(val, a[i]); } sort(a + 1, a + 1 + n); reverse(a + 1, a + 1 + n); for (len = val; len <= sum ; len++) { if (sum % len) continue; cnt = sum / len; // 原始木棍长度为len ,共 cnt 根 memset(v, 0, sizeof(v) ); if (dfs(1, 0, 1)) break; } cout << len << endl; } return 0; }
迭代加深
-
Iterative Deepening Depth-First Search，缩写 IDDFS -
从小到大限制搜索的深度，如果在当前搜索深度限制下搜不到答案，就把深度限制增加，重新进行一次搜索
-
这就是迭代加深思想
-
虽然会存在重复搜索，但是随着层数的深入，每层节点的增长会呈指数级增长，这点重复搜索与深层子树的规模相比，小巫见大巫
-
当搜索树规模随着层次的深入增长很快，并且我们能确保答案在一个较浅层的节点时，就可以采用迭代加深的深度优先搜索来解决问题
Addition Chains
-
第一个数是1，最后一个数是 n 在中间补充数字，满足 1. 严格递增 2. 每一个数都是前面某两个数字(可以是同一个)的和，可以重复 输出任意一个长度最短的解 深度最坏是 100 ， 深度不会太大，朝着最短凑凑看 1 2 4 8 16 32 64 128， 凑出 128 的长度为 8 path[] 存储当前确定好的序列是什么 剪枝： 1. 从大到小枚举下一个数字 2. 判重，如果之前和已经搜索过，就不用再搜索 -
#include <bits/stdc++.h> using namespace std; const int N = 110; int n, path[N]; // 当前枚举到的深度 bool dfs(int u, int depth) { if (u == depth) return path[u - 1] == n; // 用来判重 bool st[N] = {0}; for (int i = u - 1; i >= 0; i--) { // 剪枝，从大到小开始搜索，优化搜索顺序 for (int j = i; j >= 0; j--) { int s = path[i] + path[j]; // st[s] 用来排除等效冗余，避免搜索同一个和 if (s >= path[u - 1] && s <= n && !st[s]) { st[s] = true; path[u] = s; if (dfs(u + 1, depth)) return 1; } } } return 0; } int main() { while (cin >> n, n) { int depth = 1; path[0] = 1; while (!dfs(1, depth)) depth++; for (int i = 0; i < depth; i++) cout << path[i] << " "; cout << endl; } return 0; }
双向搜索
- 除了迭代加深之外，双向搜索也可以避免在深层子树上浪费时间
- 在一些题目中，问题不但具有
初态，还具有明确的终态，并且从初态开始搜索与从终态开始逆向搜索产生的搜索树都能覆盖整个状态空间 双向搜索： 从初态和终态出发各搜索一半状态，产生两颗深度减半的搜索树，在中间交会、组合成最终的答案
P10484 送礼物
-
背包问题的时间复杂度是 NV 时间复杂度： 45*2^31 爆掉 双向搜索，前 n/2 个物品能凑出的物品重量 排序判重， 继续搜索后 n/2 个物品能凑出来的物品重量， 加入当前的重量是x,则可以在预处理出的 所有重量中二分出一个 y,使得x+y<=w,且 x+y最大 优化，从大到小枚举所有重量，剪枝重量超过，减去 从大到小枚举可以更快达到重量 优化一下， 可以前 n/2 个多搜索几个，均衡一下时间 前 n/2 的时间复杂度是 2^(n/2) 后 n/2 的时间复杂度是 2^(n/2)*二分查找的时间 -
#include <bits/stdc++.h> using namespace std; typedef long long LL; const int N = 50; int n, m, k; LL a[N]; LL weight[1 << 24], cnt; LL ans; void dfs1 (int u, LL sum) { if (u > k) { weight[++cnt] = sum; return ; } dfs1 (u + 1, sum); if (sum + a[u] <= m) dfs1 (u + 1, sum + a[u]); } void dfs2 (int u, LL sum) { if (u > n) { int l = 1, r = cnt; while (l < r) { int mid = l + r + 1 >> 1; if (weight[mid] + sum <= m) l = mid; else r = mid - 1; } ans = max (ans, weight[l] + sum); return ; } dfs2 (u + 1, sum); if (sum + a[u] <= m) dfs2 (u + 1, sum + a[u]); } int main () { cin >> m >> n; for (int i = 1; i <= n; i++) cin >> a[i]; sort (a + 1, a + 1 + n, greater <int> ()); k = n / 2; dfs1 (1, 0); sort (weight + 1, weight + 1 + cnt); cnt = unique (weight + 1, weight + 1 + cnt) - weight - 1; dfs2 (k + 1, 0); cout << ans << endl; return 0; }
广度优先搜索
- 广度优先搜索：不断从队头取出状态，对于该状态面临的所有分支，把沿着每条分支到达的下一个状态（如果尚未访问过或者能够被更新成更优的解）插入队尾
- 重复执行上述过程直到队列为空
P10485 Bloxorz I
-
表示方块的状态： 立着：0 横着躺：1 竖着躺：2 坐标：x,y -
#include <bits/stdc++.h> using namespace std; const int N = 510; struct node { int x, y, lie; }; int n, m; char g[N][N]; int dis[N][N][3]; bool check(int x, int y) { if (x < 0 || x >= n || y < 0 || y >= m) return 0; return g[x][y] != '#'; } int bfs(node start, node end) { memset(dis, -1, sizeof(dis)); dis[start.x][start.y][start.lie] = 0; queue<node> q; q.push(start); // 偏移量 , 状态，方向，三个(x,y,lie)需要改变 int d[3][4][3] = { {{-2, 0, 2}, {0, 1, 1}, {1, 0, 2}, {0, -2, 1}}, // 0 立着 {{-1, 0, 1}, {0, 2, 0}, {1, 0, 1}, {0, -1, 0}}, // 1 横着躺 {{-1, 0, 0}, {0, 1, 2}, {2, 0, 0}, {0, -1, 2}}, // 2 竖着躺 }; while (!q.empty()) { auto t = q.front(); q.pop(); // 扩展t for (int i = 0; i < 4; i++) { node next; next = {t.x + d[t.lie][i][0], t.y + d[t.lie][i][1], d[t.lie][i][2]}; int x = next.x, y = next.y; if (!check(x, y)) continue; // 立着的，不能站在脆弱的格子 if (next.lie == 0 && g[x][y] == 'E') continue; if (next.lie == 1 && !check(x, y + 1)) continue; if (next.lie == 2 && !check(x + 1, y)) continue; if (dis[x][y][next.lie] == -1) { dis[x][y][next.lie] = dis[t.x][t.y][t.lie] + 1; q.push(next); } } } return dis[end.x][end.y][end.lie]; } int main() { while (scanf("%d%d", &n, &m), n || m) { for (int i = 0; i < n; i++) cin >> g[i]; node start = {-1}, end; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (g[i][j] == 'X' && start.x == -1) { if (g[i][j + 1] == 'X') start = {i, j, 1}; else if (g[i + 1][j] == 'X') start = {i, j, 2}; else start = {i, j, 0}; } else if (g[i][j] == 'O') end = {i, j, 0}; } } int res = bfs(start, end); if (res == -1) puts("Impossible"); else printf("%d\n", res); } return 0; }
P1256 显示图像
- 多个起始状态找最短路问题
-
// 有多个起点的洪水填充问题 // 把所有的起始状态全部插入队列 // 当每个点第一次被访问到的时候就是 // 离他最近的起点访问到他了 #include <bits/stdc++.h> using namespace std; const int dx[4] = {-1, 1, 0, 0}; const int dy[4] = {0, 0, -1, 1}; char s[1020][1020]; int d[1020][1020], n, m; queue<pair<int, int> > q; int main() { cin >> n >> m; for (int i = 1; i <= n; i++) scanf("%s", s[i] + 1); memset(d, -1, sizeof(d)); for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) if (s[i][j] == '1') // 多个起点入队 q.push(make_pair(i, j)), d[i][j] = 0; while (q.size()) { pair<int, int > now = q.front(); q.pop(); // 遍历四个方向 for (int i = 0; i < 4; i++) { pair<int, int> next(now.first + dx[i], now.second + dy[i]); if (next.first < 1 || next.first > n || next.second < 1 || next.second > m) continue; if (d[next.first][next.second] == -1) { d[next.first][next.second] = d[now.first][now.second] + 1; q.push(next); } } } // 输出内容 for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) printf("%d ", d[i][j]); puts(""); } return 0; }
双端队列BFS
- 在基本的广度优先搜索中，每次沿着分支的拓展都记为
一步 - 通过逐层搜索解决了从求起始状态到每个状态的最少步数的问题
- 等价于在一张边权为1的图上执行广度优先遍历，求出每个点相对于起点的最短距离（层次）
- 队列中的状态的层数满足两端性和单调性
- 从而每个状态在第一次被访问并入队时，计算出的步数即为所求
- 如果一张
边权要么是1，要么是0的无向图，满足不了单调性，我们可以通过双端队列广搜来计算- 算法的整体框架与一般的广搜类似，只是在每个节点上沿分支拓展时稍作改变
- 如果这条分支是
边权为0的边，就把沿该分支到达的新节点从队头入队；如果这条分支是边权为1的边，就像一般广搜一样从队尾入队 - 这样就能保证了任意时刻广搜队列中的节点对应的距离的只都具有
两段性和单调性
P4667 [BalticOI 2011] Switch the Lamp On (Day1)
-
/* 左上走到右下，只能沿着斜线走 边权只有 0 和 1，双端队列 */ #include <bits/stdc++.h> using namespace std; const int N = 510; typedef pair<int, int> PII; int n, m; char g[N][N]; int d[N][N]; int bfs() { memset(d, 0x3f, sizeof d); deque<PII> dq; dq.push_back({0, 0}); d[0][0] = 0; // 计算偏移量, 对角线位置 // 左上 0 ， 右上1 ，右下 3 ，左下 4 // 坐标的偏移量 int dx[] = {-1, -1, 1, 1}, dy[] = {-1, 1, 1, -1}; // 还要计算从原点到 给定位置的电线是平行还是垂直的 int ix[] = {-1, -1, 0, 0}, iy[4] = {-1, 0, 0, -1}; char cs[] = "\\/\\/"; while (dq.size()) { auto t = dq.front(); dq.pop_front(); int x = t.first, y = t.second; 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) { int w = 0; int j = x + ix[i], k = y + iy[i]; if (g[j][k] != cs[i]) w = 1; // 看是否需要更新 if (d[a][b] > d[x][y] + w) { d[a][b] = d[x][y] + w; if (w) dq.push_back({a, b}); else dq.push_front({a, b}); } } } } if (d[n][m] == 0x3f3f3f3f) return -1; else return d[n][m]; } int main() { int T = 1; //cin >> T; while (T--) { cin >> n >> m; for (int i = 0; i < n; i++) cin >> g[i]; int t = bfs(); if (t == -1) puts("NO SOLUTION"); else cout << t << endl; } return 0; }
优先队列BFS
- 对于更加具有普适性的情况，也就是每次拓展都有不同的
代价时，求出起始状态到每个状态的最小代价 - 方法一：仍然使用一般的广搜，采用一般的队列
- 不再能保证每个状态第一次入队时间就能得到最小代价，所以只能允许一个状态被多次更新、多次进出队列。不断执行搜索，直到队列为空
- 对应在最短路算法中，起始就是
SPFA
- 方法二：改用优先队列进行搜索
- 每次从队列中取出当前代价最小的状态进行拓展
- 当每个状态第一次从队列中被取出时，就得到了从起始状态到该状态的最小代价
- 优先队列 BFS 中每个状态只拓展一次，时间复杂度为
- 对应最短路算法就是 算法
- BFS总结(对应图上的边权情况)
- 问题只计最少步数，等价于在边权都为 1 的图上求最短路
- 使用普通的 BFS， 时间复杂度为
- 每个状态只访问（入队）一次，第一次入队时即为该状态的最少步数
- 问题每次扩展的代价可能是 0 或 1 ，等价于在边权只有 0 和 1 的图上求最短路
- 使用双端 BFS， 时间复杂度
- 每个状态被更新（入队）多次，只拓展一次，第一次出队时即为该状态的最小代价
- 问题每次扩展的代价是任意数值，等价于一般的最短路问题
- 使用优先队列 BFS，时间复杂度
- 每个状态被更新（入队）多次，只扩展一次，第一次出队时即为该状态的最小代价
- 使用迭代思想 + 普通的BFS，时间复杂度
- 每个状态被更新（入队）、扩展（出队）多次，最终完成搜索后，记录数组中保存了最小代价
- 使用优先队列 BFS，时间复杂度
- 问题只计最少步数，等价于在边权都为 1 的图上求最短路
UVA11367 Full Tank?
-
/* 容量为 C的车，起始为空 从起点到终点最少花多少钱 状态（编号，当前剩余油量） 总点数：100000 总边数：20000 (S,0) -> (T,0) 边： 1. (ver,c) -> (ver,c+1) if(c+1)<=c 2. (ver,c) -> (new ver , c-cost[i]) if c>= cost[i] 时间复杂度：100 * 100000 * log100000 10000000 * 10 约等于 10^8 */ #include <bits/stdc++.h> using namespace std; typedef pair<int, int> PII; typedef pair<int, PII> PIII; const int N = 1010, M = 20010, C = 1010; int n, m; int h[N], e[M], ne[M], w[M], idx; int price[N]; int dist[N][C]; bool st[N][C]; struct node { int d, u, c; bool operator <(const node a)const { return d > a.d; } }; void add(int a, int b, int c) { e[idx] = b, w[idx] = c, ne[idx] = h[a]; h[a] = idx++; } int dijkstra(int c, int start, int end) { priority_queue<node> heap; memset(dist, 0x3f, sizeof dist); memset(st, 0, sizeof st); heap.push({0, start, 0}); while (heap.size()) { auto t = heap.top(); heap.pop(); if (t.u == end) return t.d; if (st[t.u][t.c]) continue; // 之前已经搜索过了 st[t.u][t.c] = 1; if (t.c < c) { if (dist[t.u][t.c + 1] > t.d + price[t.u]) { dist[t.u][t.c + 1] = t.d + price[t.u]; heap.push({dist[t.u][t.c + 1], t.u, t.c + 1}); } } for (int i = h[t.u] ; ~i ; i = ne[i]) { int j = e[i]; if (t.c >= w[i]) { if (dist[j][t.c - w[i]] > t.d) { dist[j][t.c - w[i]] = t.d; heap.push({t.d, j, t.c - w[i]}); } } } } return -1; } int main() { cin >> n >> m; for (int i = 0; i < n; i++) cin >> price[i]; memset(h, -1, sizeof(h)); while (m--) { int a, b, c; cin >> a >> b >> c; add(a, b, c), add(b, a, c); } int query; cin >> query; while (query--) { int c, s, e; cin >> c >> s >> e; int t = dijkstra(c, s, e); if (t == -1) puts("impossible"); else cout << t << endl; } return 0; }
双向 BFS
- 从起始状态、目标状态分别开始，两边轮流进行，每次各拓展一整层
- 当两边各自有一个状态在记录数组中发生重复时，就说明这两个搜索过程相遇了，可以合并得出起点到终点的最少步数
P10487 Nightmare II
-
/* 男（三步）女（一步）鬼（上下左右四个方向两个单位） 鬼会到达两步之内能到达的地方，变为自己的领地 双向宽搜索，按照秒来搜索，注意可以原地不动 每一秒宽搜，男孩三步以内能到的位置标记出来 女孩一步以内能到的位置标记出来， 如果存在同一秒的是，两个会在同一个位置且当前位置没有鬼 判断这个位置是否有鬼，可以判断这个位置和鬼的曼哈顿距离是否超过2K 时间复杂度 O（n）,每个各自只会被遍历一次 */ #include <bits/stdc++.h> using namespace std; typedef pair<int, int > PII; const int N = 810; int n, m; char g[N][N]; int st[N][N]; PII ghost[2], boy, girl; bool check(int x, int y, int step) { if (x < 0 || x >= n || y < 0 || y >= m || g[x][y] == 'X' ) return 0; for (int i = 0; i < 2; i++) { if (abs(x - ghost[i].first) + abs(y - ghost[i].second) <= step * 2) return 0; } return 1; } int bfs() { int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1}; int cnt = 0; memset(st, 0, sizeof st); for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) if (g[i][j] == 'M') boy = {i, j}; else if (g[i][j] == 'G') girl = {i, j}; else if (g[i][j] == 'Z') ghost[cnt++] = {i, j}; int step = 0; queue<PII> qb, qg; qb.push(boy), qg.push(girl); // 双向 BFS while (qb.size() || qg.size()) { step++; // 男生一次能走三秒 for (int i = 0; i < 3; i++) { for (int j = 0, len = qb.size(); j < len ; j++) { auto t = qb.front(); qb.pop(); int x = t.first, y = t.second; if (!check(x, y, step)) continue; for (int k = 0; k < 4 ; k++) { int a = x + dx[k], b = y + dy[k]; if (check(a, b, step)) { if (st[a][b] == 2) return step; if (!st[a][b]) { st[a][b] = 1; qb.push({a, b}); } } } } } // 女生一次只能走一秒 for (int i = 0; i < 1; i++) { for (int j = 0, len = qg.size(); j < len ; j++) { auto t = qg.front(); qg.pop(); int x = t.first, y = t.second; if (!check(x, y, step)) continue; for (int k = 0; k < 4 ; k++) { int a = x + dx[k], b = y + dy[k]; if (check(a, b, step)) { if (st[a][b] == 1) return step; if (!st[a][b]) { st[a][b] = 2; qg.push({a, b}); } } } } } } return -1; } int main() { int T; cin >> T; while (T--) { cin >> n >> m; for (int i = 0; i < n; i++) cin >> g[i]; printf("%d\n", bfs()); } return 0; }
Problem
- Status
- Done
- Problem
- 54
- Open Since
- 2025-11-14 0:00
- Deadline
- 2026-2-6 23:59
- Extension
- 24 hour(s)