1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
| #include <iostream>
#include <cstring>
#include <queue>
#include <cstdio>
#define MAXN 55
#define INF 0x3f3f3f3f
using namespace std;
int n;
int a[MAXN*MAXN][2], b[MAXN*MAXN][2];
int an = 0, bn = 0;
char mp[MAXN][MAXN];
bool flag[MAXN][MAXN];
const int xp[] = {-1, 1, 0, 0};
const int yp[] = {0, 0, -1, 1};
bool in(int x,int y)
{
return x>0 && x<=n && y>0 && y<=n;
}
queue< pair<int, int> > q;
void mk(int x, int y, int res[MAXN][2], int &cnt)
{
memset(flag, false, sizeof(flag));
while (!q.empty())
q.pop();
res[++cnt][0] = x;
res[cnt][1] = y;
flag[x][y] = true;
q.push( pair<int, int>(x, y) );
while (!q.empty())
{
int x = q.front().first;
int y = q.front().second;
q.pop();
for (int i = 0; i<4; i++)
if ( flag[x + xp[i]][y + yp[i]] == false && mp[x+xp[i]][y+yp[i]]=='0' && in(x+xp[i], y+yp[i]))
{
flag[x + xp[i]][y + yp[i]] = true;
res[++cnt][0] = x + xp[i];
res[cnt][1] = y + yp[i];
q.push( pair<int ,int >(x + xp[i], y + yp[i]) );
}
}
}
int main()
{
cin >> n;
int sx, sy, ex, ey;
cin >> sx >> sy;
cin >> ex >> ey;
for (int i = 1; i<=n; i++)
{
for (int j = 1; j<=n; j++)
cin >> mp[i][j];
getchar();
}
mk(sx, sy, a, an);
mk(ex, ey, b, bn);
int ans = INF;
for (int i = 1; i<=an; i++)
for (int j = 1; j<=bn; j++)
{
int xd = a[i][0] - b[j][0];
int yd = a[i][1] - b[j][1];
ans = min(ans, xd * xd + yd * yd);
}
cout << ans << endl;
}
|