65 lines
1.3 KiB
C++
65 lines
1.3 KiB
C++
#include <bits/stdc++.h>
|
||
using namespace std;
|
||
|
||
int main() {
|
||
ios::sync_with_stdio(false);
|
||
cin.tie(nullptr);
|
||
|
||
int N;
|
||
cin >> N;
|
||
|
||
vector<string> g(N);
|
||
for (int i = 0; i < N; ++i) cin >> g[i];
|
||
|
||
int sx, sy, tx, ty;
|
||
cin >> sx >> sy >> tx >> ty;
|
||
|
||
// 题目样例看起来是 1-based，下标转 0-based
|
||
--sx; --sy; --tx; --ty;
|
||
|
||
auto id = [N](int x, int y) {
|
||
return x * N + y;
|
||
};
|
||
|
||
vector<int> dist(N * N, -1);
|
||
queue<int> q;
|
||
|
||
if (g[sx][sy] == '1' || g[tx][ty] == '1') {
|
||
cout << -1 << '\n';
|
||
return 0;
|
||
}
|
||
|
||
dist[id(sx, sy)] = 0;
|
||
q.push(id(sx, sy));
|
||
|
||
int dx[4] = {-1, 1, 0, 0};
|
||
int dy[4] = {0, 0, -1, 1};
|
||
|
||
while (!q.empty()) {
|
||
int u = q.front();
|
||
q.pop();
|
||
|
||
int x = u / N;
|
||
int y = u % N;
|
||
|
||
if (x == tx && y == ty) {
|
||
cout << dist[u] << '\n';
|
||
return 0;
|
||
}
|
||
|
||
for (int k = 0; k < 4; ++k) {
|
||
int nx = x + dx[k];
|
||
int ny = y + dy[k];
|
||
if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
|
||
if (g[nx][ny] == '1') continue; // 陆地不能走
|
||
int v = id(nx, ny);
|
||
if (dist[v] != -1) continue;
|
||
dist[v] = dist[u] + 1;
|
||
q.push(v);
|
||
}
|
||
}
|
||
|
||
cout << -1 << '\n';
|
||
return 0;
|
||
}
|