cf1064D. Labyrinth(01BFS)
程序员文章站
2022-08-17 17:00:31
题意 "题目链接" 给出一个$n \times m$的网格,给出起始点,要求向左走不超过$L$步,向右走不超过$R$步,求出能遍历到哪些点 Sol 一个很直观的想法,BFS的时候状态里记录下还能向左 / 右走多少步,然后xjbBFS,恭喜你fst了。。 正解非常的巧妙: 可以这样想:如果我们保证了到 ......
题意
给出一个\(n \times m\)的网格,给出起始点,要求向左走不超过\(l\)步,向右走不超过\(r\)步,求出能遍历到哪些点
sol
一个很直观的想法,bfs的时候状态里记录下还能向左 / 右走多少步,然后xjbbfs,恭喜你fst了。。
正解非常的巧妙:
可以这样想:如果我们保证了到达一个点时向左走的次数最少,那么是不是也可以保证向右走的次数最少呢?
答案是肯定的,因为向右走了一次之后肯定需要向左走一次来抵消掉这次操作
向右同理
把向左/右的边权看成1,向上/下的边权看成0,一波spfa01bfs
#include<bits/stdc++.h> const int maxn = 2001; int n, m, r, c, x, y, vis[maxn][maxn], ans, xx[4] = {-1, +1, 0, 0}, yy[4] = {0, 0, -1, +1}; char s[maxn][maxn]; struct node { int x, y, l, r; }; main() { std::cin >> n >> m >> r >> c >> x >> y; for(int i = 1; i <= n; i++) scanf("%s", s[i] + 1); std::deque<node> q; q.push_back((node) {r, c, x, y}); while(!q.empty()) { node p; p = q.front(); q.pop_front(); if(vis[p.x][p.y] || (p.l < 0) || (p.r < 0)) continue; vis[p.x][p.y] = 1; ans++; for(int i = 0; i < 4; i++) { int wx = p.x + xx[i], wy = p.y + yy[i]; if(wx < 1 || wx > n || wy < 1 || wy > m || (s[wx][wy] == '*') || (vis[wx][wy])) continue; if(i == 0 || i == 1) {q.push_front((node) {wx, wy, p.l, p.r}); continue;} if(i == 2) {q.push_back((node) {wx, wy, p.l - 1, p.r}); continue;} if(i == 3) q.push_back((node) {wx, wy, p.l, p.r - 1}); } } printf("%d", ans); }
下一篇: iOS面试题宝典(-)
推荐阅读
-
SPOJ KATHTHI - KATHTHI(01BFS)
-
cf1064D. Labyrinth(01BFS)
-
Labyrinth【BFS+优先队列】
-
Codeforces contest 1064 problem D Labyrinth —— 带位置信息的bfs
-
codeforces-D- Labyrinth
-
codeforces 1064 D. Labyrinth(bfs+记忆化)
-
CodeForces 1064D Labyrinth (bfs+优先队列)
-
codeforces 1064D. Labyrinth(BFS优先队列优化)
-
cf1064D. Labyrinth(01BFS)
-
【01BFS+思维】Codeforces Round #516 D. Labyrinth