RUPC day3: AA グラフ (AA Graph)

問題概要

https://onlinejudge.u-aizu.ac.jp/#/challenges/sources/VPC/HUPC/2869

アスキーアートでグラフが与えられるので最短経路を求める問題。
個人的にすごく好き。

注意するとこ

　　○｜○○○
　　○｜○G○
　　○｜○○○
この場合はうまく弾かないと行けない。

#include<bits/stdc++.h>
using ll = long long;
#define int ll
#define INF 1e9
#define EPS 0.0000000001
#define rep(i,n) for(int i=0;i<n;i++)
#define all(in) in.begin(), in.end()
int dx[]={0,0,2,-2};
int dy[]={2,-2,0,0};
int _dx[]={0,0,1,-1};
int _dy[]={1,-1,0,0};
int W,H;
bool inrange(int x,int y){return (0<=x&&x<W)&&(0<=y&&y<H);}
using namespace std;
typedef pair<int, int> pii;
#define MP make_pair
signed main(){
    char s,t;
    cin >> H >> W >> s >> t;
    vector<string>grid(H);
    vector<vector<pii>>edge(100);
    map<int,pii>memo;
    rep(i,H) cin >> grid[i];
    rep(i,H)rep(j,grid[i].size()){
        if('A' <= grid[i][j] && grid[i][j] <= 'Z'  ){
            memo[grid[i][j] - 'A'] = MP(j,i);
        }
    }
    for(auto itr : memo){
        int vertex = itr.first;
        pii pos = itr.second;
        rep(i,4){
            pii temp = MP(pos.first+dx[i],pos.second+dy[i]);
            if(!inrange(temp.first,temp.second))continue;
            if(grid[temp.second][temp.first] != '-' && grid[temp.second][temp.first] != '|') continue;
            if(grid[temp.second][temp.first] == '|' && ( i > 1)) continue;
            if(grid[temp.second][temp.first] == '-' && ( i <= 1))continue;
            pii now = temp;
            while(true){
                if('A' <= grid[now.second][now.first] && grid[now.second][now.first] <= 'Z'  )
                    break;
                now.first += _dx[i];
                now.second += _dy[i];
                assert(inrange(now.first, now.second));
            }
            int next =  grid[now.second][now.first] - 'A';
            edge[vertex].push_back(pii(next,1));
        }
    }
    // dijkstra
    vector<int>d(t,INF);
    d[s-'A'] = 0;
    priority_queue<pii,vector<pii>,greater<pii>>que;
    que.push(pii(0,s-'A'));
    while(!que.empty()){
        pii now = que.top();
        que.pop();
        if(now.first > d[now.second])continue;
        rep(i,edge[now.second].size()){
            int next  = edge[now.second][i].first;
            if(d[next] < 1 + now.first) continue;
            d[next] = 1 + now.first;
            que.push(pii(d[next],next));
        }
    }
    cout << d[t-'A'] << endl;
}