# AOJ RitsCamp18Day3: C. AA グラフ (AA Graph)

,

https://onlinejudge.u-aizu.ac.jp/beta/room.html#RitsCamp18Day3/problems/C

## implementation

#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; (i) < int(n); ++ (i))
using namespace std;

const int dy[] = { -1, 1, 0, 0 };
const int dx[] = { 0, 0, 1, -1 };
const char *type = "||--";
vector<vector<int> > parse(int h, int w, vector<string> const & f) {
auto is_on_field = [&](int y, int x) { return 0 <= y and y < h and 0 <= x and x < w; };
vector<vector<int> > g(26);
REP (y, h) REP (x, w) if (isupper(f[y][x])) {
REP (i, 4) {
int ny = y + dy[i];
int nx = x + dx[i];
while (is_on_field(ny, nx) and (f[ny][nx] == 'o' or f[ny][nx] == type[i])) {
ny += dy[i];
nx += dx[i];
}
if (is_on_field(ny, nx) and isupper(f[ny][nx])) {
g[f[y][x] - 'A'].push_back(f[ny][nx] - 'A');
}
}
}
return g;
}

vector<int> breadth_first_search(int root, vector<vector<int> > const & g) {
int n = g.size();
vector<int> dist(n, INT_MAX);
queue<int> que;
dist[root] = 0;
que.push(root);
while (not que.empty()) {
int i = que.front(); que.pop();
for (int j : g[i]) if (dist[j] == INT_MAX) {
dist[j] = dist[i] + 1;
que.push(j);
}
}
return dist;
}

int main() {
// input
int h, w; cin >> h >> w;
char start, goal; cin >> start >> goal;
vector<string> f(h);
REP (y, h) cin >> f[y];

// solve
vector<vector<int> > g = parse(h, w, f);
vector<int> dist = breadth_first_search(start - 'A', g);
int result = dist[goal - 'A'];

// output
cout << result << endl;
return 0;
}