#include <iostream>
#include <queue>
using namespace std;
int _N, _Res;
int _DxDy[4][2] = { {1, 0}, {0, 1}, {-1, 0}, {0, -1} };;
string _Str;
bool _Map[50][50];
bool _IsVisted[50][50];
priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> _BfsQueue;
int main()
{
cin >> _N;
for (int i = 0; i < _N; i++) {
cin >> _Str;
for (int j = 0; j < _N; j++)
if (_Str[j] == '1')
_Map[i][j] = true;
}
_BfsQueue.push(make_pair(0, make_pair(0, 0)));
_IsVisted[0][0] = true;
while (!_BfsQueue.empty()) {
pair<int, int> _Pos = _BfsQueue.top().second;
int _Cnt = _BfsQueue.top().first;
_BfsQueue.pop();
if (_Pos.first == _N - 1 && _Pos.second == _N - 1) {
_Res = _Cnt;
break;
}
for (int i = 0; i < 4; i++) {
int _dx = _Pos.first + _DxDy[i][0];
int _dy = _Pos.second + _DxDy[i][1];
if (_dx >= _N || _dy >= _N || _dx < 0 || _dy < 0)
continue;
if (_IsVisted[_dx][_dy]) continue;
_IsVisted[_dx][_dy] = true;
if (!_Map[_dx][_dy]) _BfsQueue.push(make_pair(_Cnt + 1, make_pair(_dx, _dy)));
else _BfsQueue.push(make_pair(_Cnt, make_pair(_dx, _dy)));
}
}
cout << _Res;
return 0;
}
#99클럽 #코딩테스트준비 #개발자취업 #항해99 #TIL