RUPC2018 day3 C： AA グラフ (AA Graph)

問題ページ
Aizu Online Judge Arena

解法

やること自体は簡単で与えられた二次元グリッド上でつながっている頂点同士をつないだグラフをつくり、あとはdijkstraなりワーシャルフロイドを貼るだけ。ただし実装が非常にバグらせやすいので要注意。
以下に示したソースコードの実装は
1 各文字が存在する場所を覚えておく
2 各文字から4方向に探索していく
3 アルファベットの位置から2つ進んだ場所が正しい向きの辺でなければ終了
4 アルファベットがあればそのアルファベットと辺をつなぐ
5 '.'があれば探索終了
6 グラフが構築できるのであとはdijkstraを貼る

以下のケースがやばで実装サボってると落ちやすいので注意

ooo|ooo
oAo|oBo
ooo|ooo

ソースコード

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

string a[55];
vector<PII> g[30];
signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  int h, w;
  char st, t;
  cin >> h >> w >> st >> t;
  REP(i, h) cin >> a[i];

  vector<PII> pos(26, {-1, -1});
  REP(i, h) REP(j, w) {
    if('A' <= a[i][j] && a[i][j] <= 'Z') {
      pos[a[i][j]-'A'] = {i, j};
    }
  }

  REP(i, 26) {
    if(pos[i] == PII{-1, -1}) continue;
    REP(j, 4) {
      int x = pos[i].second + 2*dx[j], y = pos[i].first + 2*dy[j];
      if(!IN(0LL, w, x) || !IN(0LL, h, y)) continue;
      if(dx[j] != 0 && a[y][x] != '-') continue;
      if(dy[j] != 0 && a[y][x] != '|') continue;
      while(IN(0LL, w, x) && IN(0LL, h, y)) {
        if('A' <= a[y][x] && a[y][x] <= 'Z') {
          g[i].PB({a[y][x]-'A', 1});
          g[a[y][x]-'A'].PB({i, 1});
          break;
        } else if(a[y][x] != '.') {
          x += dx[j], y += dy[j];
        } else {
          break;
        }
      }
    }
  }

  VI d(30);
  auto dijkstra = [&](int s) {
    d.assign(30, INF);
    d[s] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> que;
    que.push(PII{d[s], s});

    while(que.size()) {
      PII p = que.top(); que.pop();
      // cout << p << endl;
      int v = p.second;
      if(d[v] < p.first) continue;
      for(PII &e: g[v]) {
        if(d[e.first] > d[v] + e.second) {
          d[e.first] = d[v] + e.second;
          que.push(PII{d[e.first], e.first});
        }
      }
    }
  };
  dijkstra(st-'A');
  cout << d[t-'A'] << endl;

  return 0;
}