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
| #include <bits/stdc++.h>
#define ouo ios_base::sync_with_stdio(false), cin.tie(0)
#define ll long long
#define db double
using namespace std;
int n;
int high = -1, low = 0;
int g[305][305];
int viewed[305][305];
queue<pair<pair<int, int>, int>> todo;
int dir[4][2] = {
{0, 1},
{0, -1},
{1, 0},
{-1, 0}
};
int bin_s(int m) {
todo.push(make_pair(make_pair(0, 0), 0));
viewed[0][0] = 1;
while (!todo.empty()) {
int x = todo.front().first.first;
int y = todo.front().first.second;
int cnt = todo.front().second;
viewed[x][y] = 1;
todo.pop();
if (x == n - 1 && y == n - 1) {
return cnt;
}
for (int i = 0; i < 4; i++) {
int nx = x + dir[i][0];
int ny = y + dir[i][1];
if (nx >= 0 && nx <= n - 1 && ny >= 0 && ny <= n - 1 && viewed[nx][ny] == 0) {
int h = abs(g[x][y] - g[nx][ny]);
if (h <= m) {
viewed[nx][ny] = 1;
todo.push(make_pair(make_pair(nx, ny), cnt + 1));
}
}
}
}
return -1;
}
int main() {
cin >> n;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> g[i][j];
high = max(g[i][j], high);
}
}
while (high - low > 1) {
while (!todo.empty()) todo.pop();
memset(viewed, 0, sizeof(viewed));
int m = low + (high - low) / 2;
int check = bin_s(m);
if (check == -1) {
low = m;
} else {
high = m;
}
}
cout << high << "\n";
while (!todo.empty()) todo.pop();
memset(viewed, 0, sizeof(viewed));
cout << bin_s(high);
return 0;
}
|