/* ID: espr1t TASK: KEYWORDS: */ #include #include #include #include using namespace std; FILE *in; FILE *out; const int MAX = 1024; const int INF = 10000001; int n, m; int a[MAX][MAX]; int price[MAX * MAX]; int nextIdx; int idx[MAX][MAX]; vector v[MAX * MAX]; int bfs(int snode, int enode) { memset(price, 63, sizeof(price)); queue q; q.push(snode); price[snode] = 0; while (!q.empty()) { int node = q.front(); q.pop(); if (node == enode) return price[node]; for (int i = 0; i < (int)v[node].size(); i++) { if (price[v[node][i]] > INF) { price[v[node][i]] = price[node] + 1; q.push(v[node][i]); } } } return -1; } int main(void) { in = stdin; out = stdout; in = fopen("ice.in", "rt"); out = fopen("ice.out", "wt"); fscanf(in, "%d", &n); m = n; for (int i = 0; i < n; i++) for (int c = 0; c < m; c++) fscanf(in, "%d", &a[i][c]); nextIdx = 0; memset(idx, -1, sizeof(idx)); for (int i = 0; i < n; i++) { for (int c = 0; c < m; c++) { if (a[i][c] == 0) idx[i][c] = nextIdx++; } } // Horizontal for (int row = 0; row < n; row++) { int prev = -1; for (int col = 0; col < m; col++) { if (idx[row][col] != -1) { if (prev != -1) { v[prev].push_back(idx[row][col]); v[idx[row][col]].push_back(prev); } prev = idx[row][col]; } } } // Vertical for (int col = 0; col < m; col++) { int prev = -1; for (int row = 0; row < n; row++) { if (idx[row][col] != -1) { if (prev != -1) { v[prev].push_back(idx[row][col]); v[idx[row][col]].push_back(prev); } prev = idx[row][col]; } } } int srow, scol; fscanf(in, "%d %d", &srow, &scol), srow--, scol--; int erow, ecol; fscanf(in, "%d %d", &erow, &ecol), erow--, ecol--; fprintf(out, "%d\n", bfs(idx[srow][scol], idx[erow][ecol])); return 0; }