#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define mp make_pair
#define F first
#define S second
constexpr int maxn = 4000;
int h, w;
char grid[maxn][maxn];
int dist[maxn][maxn];
pii dir[4] = {mp(1, 0), mp(-1, 0), mp(0, 1), mp(0, -1)};
deque<pii> q;
pii vsum(pii a, pii b) { return mp(a.F + b.F, a.S + b.S); }
int main() {
// ios_base::sync_with_stdio(false);
// cin.tie(NULL);
cin >> h >> w;
for (int r = 0; r < h; r++) {
for (int c = 0; c < w; c++) {
cin >> grid[r][c];
dist[r][c] = maxn * maxn;
}
}
// for (auto p : dir) cout << p.F << ' ' << p.S << '\n';
dist[0][0] = 0;
q.push_front(mp(0, 0));
while (!q.empty()) {
pii cell = q.front();
q.pop_front();
for (int i = 0; i < 4; i++) {
pii nbr = vsum(cell, dir[i]);
if (nbr.F < 0 || nbr.F >= h || nbr.S < 0 || nbr.S >= w) continue;
if (grid[nbr.F][nbr.S] == '.') continue;
int wgt = (grid[cell.F][cell.S] == grid[nbr.F][nbr.S] ? 0 : 1);
// cout << "checked " << cell.F << cell.S << " " << nbr.F << nbr.S << '\t' << wgt << '\n';
if (dist[cell.F][cell.S] + wgt < dist[nbr.F][nbr.S]) {
dist[nbr.F][nbr.S] = dist[cell.F][cell.S] + wgt;
if (wgt == 1)
q.push_back(nbr);
else
q.push_front(nbr);
}
}
}
int ans = 0;
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
// cout << (dist[i][j] == maxn * maxn ? -1 : dist[i][j]) << '\t';
if (grid[i][j] != '.') ans = max(ans, dist[i][j]);
}
// cout << '\n';
}
cout << ans + 1 << '\n';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
29 ms |
5464 KB |
Output is correct |
2 |
Correct |
1 ms |
468 KB |
Output is correct |
3 |
Correct |
1 ms |
596 KB |
Output is correct |
4 |
Correct |
16 ms |
5076 KB |
Output is correct |
5 |
Correct |
7 ms |
2900 KB |
Output is correct |
6 |
Correct |
1 ms |
468 KB |
Output is correct |
7 |
Correct |
1 ms |
596 KB |
Output is correct |
8 |
Correct |
1 ms |
724 KB |
Output is correct |
9 |
Correct |
1 ms |
1108 KB |
Output is correct |
10 |
Correct |
6 ms |
2584 KB |
Output is correct |
11 |
Correct |
4 ms |
2112 KB |
Output is correct |
12 |
Correct |
9 ms |
3028 KB |
Output is correct |
13 |
Correct |
8 ms |
3004 KB |
Output is correct |
14 |
Correct |
8 ms |
2916 KB |
Output is correct |
15 |
Correct |
24 ms |
5460 KB |
Output is correct |
16 |
Correct |
24 ms |
5352 KB |
Output is correct |
17 |
Correct |
21 ms |
5248 KB |
Output is correct |
18 |
Correct |
15 ms |
5076 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
31164 KB |
Output is correct |
2 |
Correct |
120 ms |
17856 KB |
Output is correct |
3 |
Correct |
1073 ms |
94200 KB |
Output is correct |
4 |
Correct |
263 ms |
33520 KB |
Output is correct |
5 |
Correct |
603 ms |
67880 KB |
Output is correct |
6 |
Correct |
1371 ms |
107876 KB |
Output is correct |
7 |
Correct |
17 ms |
32596 KB |
Output is correct |
8 |
Correct |
17 ms |
31060 KB |
Output is correct |
9 |
Correct |
5 ms |
684 KB |
Output is correct |
10 |
Correct |
3 ms |
452 KB |
Output is correct |
11 |
Correct |
17 ms |
31936 KB |
Output is correct |
12 |
Correct |
2 ms |
1600 KB |
Output is correct |
13 |
Correct |
123 ms |
17872 KB |
Output is correct |
14 |
Correct |
77 ms |
11900 KB |
Output is correct |
15 |
Correct |
76 ms |
13012 KB |
Output is correct |
16 |
Correct |
53 ms |
6608 KB |
Output is correct |
17 |
Correct |
304 ms |
36068 KB |
Output is correct |
18 |
Correct |
280 ms |
35832 KB |
Output is correct |
19 |
Correct |
282 ms |
33484 KB |
Output is correct |
20 |
Correct |
238 ms |
31100 KB |
Output is correct |
21 |
Correct |
628 ms |
70064 KB |
Output is correct |
22 |
Correct |
611 ms |
67816 KB |
Output is correct |
23 |
Correct |
580 ms |
56884 KB |
Output is correct |
24 |
Correct |
606 ms |
69348 KB |
Output is correct |
25 |
Correct |
1177 ms |
94196 KB |
Output is correct |
26 |
Correct |
969 ms |
130956 KB |
Output is correct |
27 |
Correct |
1274 ms |
121148 KB |
Output is correct |
28 |
Correct |
1373 ms |
107884 KB |
Output is correct |
29 |
Correct |
1370 ms |
106180 KB |
Output is correct |
30 |
Correct |
1389 ms |
110184 KB |
Output is correct |
31 |
Correct |
1018 ms |
73392 KB |
Output is correct |
32 |
Correct |
1312 ms |
109516 KB |
Output is correct |