HW盤面のBFSをグラフ構築してから解く

グラフの問題を練習してて、よくあるHW盤面の問題をグラフ構築してから実装してみたのでそのメモ

問題

これを解いていく。HW盤面の迷路の最も基本的な形。

atcoder.jp

※以下の2パターンの実装、書いた時期が違うので書き方の癖が違って読みにくいです、、

HW盤面そのまま解く場合

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template <class T>
using vec = std::vector<T>;
const int IINF = 0x3f3f3f3f;  // 2倍しても負にならない
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;

int main() {
  vec<int> dx = {1, 0, -1, 0};
  vec<int> dy = {0, 1, 0, -1};

  int n, m;
  int sx, sy;
  int gx, gy;
  cin >> n >> m >> sx >> sy >> gx >> gy;
  sx--;
  sy--;
  gx--;
  gy--;

  vector<vector<char>> c(n, vector<char>(m, '.'));
  for (size_t i = 0; i < n; i++) {
    for (size_t j = 0; j < m; j++) {
      cin >> c.at(i).at(j);
    }
  }

  vec<vec<int>> dist(n, vec<int>(m, IINF));  // 最短距離をメモ
  dist.at(sx).at(sy) = 0;                    // スタート地点は距離0
  queue<pair<int, int>> que;                 // bfsのためのキュー

  que.push(make_pair(sx, sy));
  while (que.size()) {
    // 取り出して探索
    auto pos = que.front();
    que.pop();

    // 近傍で探索していない箇所の距離を確定
    for (int i = 0; i < 4; i++) {
      // 次の位置
      int nx = pos.first + dx.at(i);
      int ny = pos.second + dy.at(i);

      // 範囲外の場合
      if (nx < 0 || nx >= n || ny < 0 || ny >= m) {
        continue;
      }
      // 通行不可の場合
      if (c.at(nx).at(ny) == '#') {
        continue;
      }
      // 未探索なら現在地から+1で距離確定して, キューに追加
      if (dist.at(nx).at(ny) == IINF) {
        dist.at(nx).at(ny) = dist.at(pos.first).at(pos.second) + 1;
        que.push(make_pair(nx, ny));
      }
    }
  }

  cout << dist.at(gx).at(gy) << endl;
}

グラフ構築してから解く場合

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int IINF = 0x3f3f3f3f;  // 2倍しても負にならない
#define all(obj) (obj).begin(), (obj).end()
using Graph = vector<vector<int>>;

// 変数宣言------------------
int n, m;
Graph g((int)1e5 + 9);
int dist[(int)1e5 + 9];
int h, w;
int sx, sy, gx, gy;

// メイン------------------
int main() {
  cin >> h >> w;
  cin >> sy >> sx >> gy >> gx;
  sy--, sx--, gy--, gx--;

  // 距離の初期化
  for (int i = 0; i < (int)1e5 + 9; i++) {
    dist[i] = IINF;
  }

  // 入力
  char maze[h][w];
  char c;
  for (int i = 0; i < h; i++) {
    for (int j = 0; j < w; j++) {
      cin >> c;
      maze[i][j] = c;
    }
  }

  // グラフ構築
  for (int i = 0; i < h; i++) {
    for (int j = 0; j < w; j++) {
      if (maze[i][j] == '#') {
        continue;
      }

      // 現在の頂点
      int now = i * w + j;

      // 右の頂点に辺を張る
      if (j + 1 < w && maze[i][j + 1] != '#') {
        g[now].push_back(now + 1);
        g[now + 1].push_back(now);
      }

      // 下の頂点に辺を張る
      if (i + 1 < h && maze[i + 1][j] != '#') {
        g[now].push_back(now + w);
        g[now + w].push_back(now);
      }
    }
  }

  int start = sy * w + sx;
  int goal = gy * w + gx;


  queue<int> que;
  que.push(start);
  dist[start] = 0;

  // bfs
  while (!que.empty()) {
    int now = que.front();
    que.pop();

    for (int i = 0; i < g[now].size(); i++) {
      int next = g[now][i];
      if (dist[next] == IINF) {
        que.push(next);
      }
      dist[next] = min(dist[next], dist[now] + 1);
    }
  }

  cout << dist[goal];

  // 動作確認用
  // for (int i = 0; i < h; i++) {
  //   for (int j = 0; j < w; j++) {
  //     if (dist[i * w + j] == IINF) {
  //       cout << setw(2) << '*' << " ";
  //     } else {
  //       cout << setw(2) << dist[i * w + j] << " ";
  //     }
  //   }
  //   cout << endl;
  // }
}