#include #include #include #include #include #include using namespace std; vector grid; struct step_struct { pair coord; int len; }; int spath (void); int main (void) { string inp; while (getline (cin, inp)) grid.push_back (inp); cout << spath () << endl; return 0; } int spath (void) { pair p; queue wl; map, int> seen; step_struct step1, step2; int i, j, min_len; min_len = grid.size () * grid [0].size () + 5; p.first = 0; p.second = 0; seen [p] = 1; step1.coord = p; step1.len = 1; wl.push (step1); while (!wl.empty ()) { step1 = wl.front (); wl.pop (); if (step1.coord.first == grid.size () - 1 && step1.coord.second == grid [0].size () - 1) { min_len = min (step1.len, min_len); } for (i = -1; i < 2; i++) { for (j = -1; j < 2; j++) { p.first = step1.coord.first + i; p.second = step1.coord.second + j; if (p.first < 0 || p.first >= grid.size () || p.second < 0 || p.second >= grid [0].size ()) continue; if (seen [p]) continue; if (grid [p.first][p.second] == 'O') { step2.coord = p; step2.len = step1.len + 1; wl.push (step2); seen [p] = 1; } } } } return min_len; }