AtCoder Beginner Contest 246 E - Bishop 2 雑メモ（01-BFS, 枝刈りBFS）
01-BFSと枝刈りBFSを忘れかけていたので、見返す時用の雑なメモ 01-BFSで解ける問題は、枝刈りBFSでも解ける問題が多いっぽい？
問題
枝刈りBFS
- 基本は通常のBFS
- 「明らかに探索しなくていいいパターン」が出現したら、その頂点以降の探索を打ち切る
01-BFS
- 次の点へのコストを0 or 1として考える
- 最短距離がなるべく小さい点から探索したいので、以下のようにdequeを使って探索する頂点を以下のように管理する
- 次のコストが0 → dequeの先頭に追加
- 次のコストが1 → dequeの末尾に追加
実装
枝刈り全探索
#include <bits/stdc++.h> #include <atcoder/all> using namespace atcoder; using namespace std; using ll = long long; const int IINF = 0x3f3f3f3f; // 2倍しても負にならない const long long LINF = 0x3f3f3f3f3f3f3f3fLL; long long MOD = 1000000007; using plint = pair<ll, ll>; using pint = pair<int, int>; #define all(obj) (obj).begin(), (obj).end() struct Edge { int from, to, cost; Edge(int f, int t, int c) : from(f), to(t), cost(c) {} }; using Graph = vector<vector<int>>; // 変数宣言------------------ // 関数定義------------------ // メイン------------------ int main() { // デバッグ用 ifstream in("input.txt"); if (in.is_open()) { cin.rdbuf(in.rdbuf()); } int n; cin >> n; int ax, ay, bx, by; cin >> ax >> ay >> bx >> by; ax--, ay--, bx--, by--; char s[n][n]; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cin >> s[i][j]; } } // ななめ4方向 vector<int> dirx = {1, -1, -1, 1}; vector<int> diry = {1, -1, 1, -1}; // d 最短手数 // q 探索キュー vector<vector<int>> d(n, vector<int>(n, IINF)); queue<pint> q; // 初期化 q.push({ax, ay}); d[ax][ay] = 0; // bfs while (!q.empty()) { auto [x, y] = q.front(); q.pop(); for (int i = 0; i < 4; i++) { for (int add = 1; add < n; add++) { int nx = x + add * dirx[i]; int ny = y + add * diry[i]; if (nx < 0 || ny < 0 || nx >= n || ny >= n || s[nx][ny] == '#') { break; } // TODO: ここで枝刈りする // 小さい時 → キューにpush // 同じ時 → 素通り // 大きい時 → 枝刈り if (d[nx][ny] > d[x][y] + 1) { q.push({nx, ny}); d[nx][ny] = d[x][y] + 1; } else if (d[nx][ny] < d[x][y] + 1) { break; } } } } if (d[bx][by] == IINF) { cout << -1 << endl; } else { cout << d[bx][by] << endl; } }
01-BFS
#include <bits/stdc++.h> #include <atcoder/all> using namespace atcoder; using namespace std; using ll = long long; const int IINF = 0x3f3f3f3f; // 2倍しても負にならない const long long LINF = 0x3f3f3f3f3f3f3f3fLL; long long MOD = 1000000007; using plint = pair<ll, ll>; using pint = pair<int, int>; #define all(obj) (obj).begin(), (obj).end() struct Edge { int from, to, cost; Edge(int f, int t, int c) : from(f), to(t), cost(c) {} }; using Graph = vector<vector<int>>; // 変数宣言------------------ // 関数定義------------------ // メイン------------------ int main() { // デバッグ用 ifstream in("input.txt"); if (in.is_open()) { cin.rdbuf(in.rdbuf()); } int n; cin >> n; int ax, ay, bx, by; cin >> ax >> ay >> bx >> by; ax--, ay--, bx--, by--; char s[n][n]; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cin >> s[i][j]; } } vector<vector<vector<int>>> d(n, vector<vector<int>>(n, vector<int>(4, IINF))); // ななめ4方向 vector<int> dx = {1, -1, -1, 1}; vector<int> dy = {1, -1, 1, -1}; // (x, y, dir); deque<tuple<int, int, int>> q; for (int i = 0; i < 4; i++) { q.push_back({ax, ay, i}); d[ax][ay][i] = 1; } while (!q.empty()) { auto [x, y, dir] = q.front(); q.pop_front(); for (int ndir = 0; ndir < 4; ndir++) { int nx = x + dx[ndir]; int ny = y + dy[ndir]; if (nx < 0 || ny < 0 || nx >= n || ny >= n || s[nx][ny] == '#') { continue; } int cost = (dir == ndir ? 0 : 1); // 距離更新できるなら, 探索対象にする if (d[nx][ny][ndir] > d[x][y][dir] + cost) { if (cost == 0) { q.push_front({nx, ny, ndir}); } else { q.push_back({nx, ny, ndir}); } } // 最短距離更新 d[nx][ny][ndir] = min(d[nx][ny][ndir], d[x][y][dir] + cost); } } // 4方向のうち, 最も小さい手数がこたえ int ans = IINF; for (int i = 0; i < 4; i++) { ans = min(ans, d[bx][by][i]); } if (ans == IINF) { cout << -1 << endl; } else { cout << ans << endl; } }
