AA Graph [RUPC2018 Day3 C]

前提知識

• ワーシャルフロイド

解法

https://onlinejudge.u-aizu.ac.jp/beta/review.html#RitsCamp18Day3/2752946

この問題は二段階で解いていく
「グラフから辺情報を抽出する」「ワーシャルフロイドで最短距離を求める」
後半はワーシャルフロイドを知っていれば一瞬なので、前半が大変になる。

「グラフから辺情報を抽出する」
色々な実装方法があるかと思うが、H,W≦50なので、時間がかかるが、やりやすい方法でやろう。
自分の実装方法を紹介しておく。
　
A～Zである全てのマスについて、上下左右に移動してA～Zがあるかを判定する。
道中にちゃんと道がある必要があるが、

• '.'が無い
• 横移動であれば'|'が無い
• 縦移動であれば'-'が無い

ことをチェックしながら上下左右に見ていく。
到達できれば辺として記録しておこう。
　
「ワーシャルフロイドで最短距離を求める」
辺情報が抽出できたら、s->tの最短距離を求めるだけだが、O(N^3)のワーシャルフロイドが余裕で間に合うので、これで求めよう。

int H, W, s, t;
string A[101];
int dx[4] = { 0, 1, 0, -1 }, dy[4] = { -1, 0, 1, 0 };
int d[26][26];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> H >> W;
    char c; cin >> c; s = c - 'A'; cin >> c; t = c - 'A';
    rep(y, 0, H) cin >> A[y];

    rep(i, 0, 26) rep(j, 0, 26) d[i][j] = inf;
    rep(i, 0, 26) d[i][i] = 0;

    rep(y, 0, H) rep(x, 0, W) if ('A' <= A[y][x] and A[y][x] <= 'Z') {
        rep(i, 0, 4) {
            int xx = x + dx[i];
            int yy = y + dy[i];
            while (0 <= xx and xx < W and 0 <= yy and yy < H) {
                if ('A' <= A[yy][xx] and A[yy][xx] <= 'Z') {
                    int a = A[y][x] - 'A';
                    int b = A[yy][xx] - 'A';
                    d[a][b] = d[b][a] = 1;
                    break;
                } else if (A[yy][xx] == '.') break;

                if (i % 2 == 0 and A[yy][xx] == '-') break;
                if (i % 2 == 1 and A[yy][xx] == '|') break;

                xx += dx[i];
                yy += dy[i];
            }
        }
    }

    rep(k, 0, 26) rep(i, 0, 26) rep(j, 0, 26) d[i][j] = min(d[i][j], d[i][k] + d[k][j]);

    cout << d[s][t] << endl;
}