#include <bits/stdc++.h>
using namespace std;
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
#define deb(x) cout<<#x<<'='<<x<<'\n';
#define deb2(x,y) cout<<#x<<'='<<x<<", "<<#y<<'='<<y<<'\n';
#define int long long
#define all(x) (x).begin(), (x).end()
#define pii pair<int, int>
#define pb push_back
#define f first
#define s second
#define sz(x) (int)(x).size()
const long double PI = acos(-1);
const int mod = 1e9 + 7, inf = 1e10;
const int D = 4010;
const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};
int n, m;
string a[D];
int d[D][D];
void solve_test() {
cin >> n >> m;
for (int i = 0; i < n; i++)
cin >> a[i];
deque<pii> q;
q.pb({0, 0});
d[0][0] = 1;
int ans = 1;
while (!q.empty()) {
pii u = q.front();
int ux = u.f, uy = u.s;
q.pop_front();
ans = max(ans, d[ux][uy]);
for (int i = 0; i < 4; i++) {
int vx = ux + dx[i];
int vy = uy + dy[i];
if (vx<0 or vx >= n or vy<0 or vy >= m)
continue;
if (a[vx][vy] == '.')
continue;
int wt = (a[ux][uy] != a[vx][vy]);
if (d[vx][vy] == 0) {
d[vx][vy] = d[ux][uy] + wt;
if (wt) q.pb({vx, vy});
else q.push_front({vx, vy});
}
}
}
cout << ans << '\n';
}
signed main() {
fastio
solve_test();
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
4892 KB |
Output is correct |
2 |
Correct |
1 ms |
452 KB |
Output is correct |
3 |
Correct |
1 ms |
560 KB |
Output is correct |
4 |
Correct |
7 ms |
4296 KB |
Output is correct |
5 |
Correct |
3 ms |
2244 KB |
Output is correct |
6 |
Correct |
1 ms |
448 KB |
Output is correct |
7 |
Correct |
1 ms |
588 KB |
Output is correct |
8 |
Correct |
1 ms |
716 KB |
Output is correct |
9 |
Correct |
1 ms |
828 KB |
Output is correct |
10 |
Correct |
3 ms |
1736 KB |
Output is correct |
11 |
Correct |
3 ms |
1764 KB |
Output is correct |
12 |
Correct |
4 ms |
2440 KB |
Output is correct |
13 |
Correct |
3 ms |
2252 KB |
Output is correct |
14 |
Correct |
2 ms |
2312 KB |
Output is correct |
15 |
Correct |
9 ms |
4512 KB |
Output is correct |
16 |
Correct |
10 ms |
4884 KB |
Output is correct |
17 |
Correct |
7 ms |
4548 KB |
Output is correct |
18 |
Correct |
7 ms |
4292 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
16116 KB |
Output is correct |
2 |
Correct |
32 ms |
15128 KB |
Output is correct |
3 |
Correct |
156 ms |
90256 KB |
Output is correct |
4 |
Correct |
68 ms |
43072 KB |
Output is correct |
5 |
Correct |
135 ms |
69140 KB |
Output is correct |
6 |
Correct |
557 ms |
184272 KB |
Output is correct |
7 |
Correct |
10 ms |
16844 KB |
Output is correct |
8 |
Correct |
9 ms |
16100 KB |
Output is correct |
9 |
Correct |
2 ms |
968 KB |
Output is correct |
10 |
Correct |
1 ms |
588 KB |
Output is correct |
11 |
Correct |
9 ms |
16464 KB |
Output is correct |
12 |
Correct |
1 ms |
1228 KB |
Output is correct |
13 |
Correct |
31 ms |
15132 KB |
Output is correct |
14 |
Correct |
19 ms |
9824 KB |
Output is correct |
15 |
Correct |
18 ms |
14252 KB |
Output is correct |
16 |
Correct |
15 ms |
6484 KB |
Output is correct |
17 |
Correct |
81 ms |
32984 KB |
Output is correct |
18 |
Correct |
73 ms |
47736 KB |
Output is correct |
19 |
Correct |
63 ms |
42984 KB |
Output is correct |
20 |
Correct |
43 ms |
27068 KB |
Output is correct |
21 |
Correct |
100 ms |
61184 KB |
Output is correct |
22 |
Correct |
136 ms |
69184 KB |
Output is correct |
23 |
Correct |
152 ms |
56152 KB |
Output is correct |
24 |
Correct |
102 ms |
59316 KB |
Output is correct |
25 |
Correct |
395 ms |
156244 KB |
Output is correct |
26 |
Correct |
347 ms |
235976 KB |
Output is correct |
27 |
Correct |
439 ms |
223160 KB |
Output is correct |
28 |
Correct |
555 ms |
182076 KB |
Output is correct |
29 |
Correct |
534 ms |
182436 KB |
Output is correct |
30 |
Correct |
490 ms |
189372 KB |
Output is correct |
31 |
Correct |
420 ms |
115300 KB |
Output is correct |
32 |
Correct |
400 ms |
195360 KB |
Output is correct |