#include #include #include #include #include #include #include #include #include #include using namespace std; int ice[1000][1000]; int n, xa, ya, xb, yb; int MOVES[][2] = { {0, -1}, {0, 1}, {1, 0}, {-1, 0} }; vector > getNeighbours(int x, int y) { vector > res; for (int i =0; i < 4; ++i) { int movex = MOVES[i][0]; int movey = MOVES[i][1]; int newX = x+movex; int newY = y+movey; if (newX >= n || newX < 0 || newY>=n || newY < 0) { continue; } if (ice[newX][newY] == 0) { // no ice res.push_back(make_pair(newX, newY)); } else { if (movex > 0) { int j=newX; while(++j=0) { if (ice[j][newY] == 0) {break;} } if (j>=0) {res.push_back(make_pair(j, newY));} } else if (movey < 0) { int k=newY; while(--k>=0) { if (ice[newX][k] == 0) {break;} } if (k>=0) {res.push_back(make_pair(newX, k));} } else if (movey > 0) { int k=newY; while(++k > q; queue resQ; bool vis[1000][1000]; memset(vis, 0, sizeof(vis)); q.push(make_pair(xa,ya)); resQ.push(0); vis[xa][ya] = true; while (!q.empty()) { pair f = q.front(); q.pop(); int dist = resQ.front(); resQ.pop(); vector > nbs = getNeighbours(f.first, f.second); for (int i = 0; i < nbs.size(); ++i) { pair nextNb = nbs[i]; if (!vis[nextNb.first][nextNb.second]) { if (nextNb.first == xb && nextNb.second == yb) { return dist+1; } vis[nextNb.first][nextNb.second] = true; resQ.push(dist+1); q.push(nextNb); } } } return -1; } int main() { freopen("ice.in", "r", stdin); freopen("ice.out", "w", stdout); scanf("%d",&n); for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { scanf("%d", &ice[i][j]); } } scanf("%d %d %d %d", &xa, &ya, &xb, &yb); xa--;ya--;xb--;yb--; printf("%d\n", bfs()); return 0; }