#include <bits/stdc++.h>
#define pb push_back
#define er erase
#define in insert
#define s(a, x, y) sort(a.begin()+x, a.begin()+y);
#define r(a, x, y) reverse(a.begin()+x, a.begin()+y);
#define mp make_pair
#define F first
#define S second
#define ll long long
#define ld long double
#define forn(i, a, b) for(int i=a; i<=b; i++)
#define form(i, a, b) for(int i=a; i>=b; i--)
#define PI 3.14159265358979
#define inf 2147483647
#define sp setprecision
#define pii pair <int, int>
#define gcd __gcd
#define endl '\n'
#define sz(a) (int)a.size()
using namespace std;
const ll N = 4000 + 13;
ll t1, n, m, d[N][N], ans, x, y;
ll dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1, 0, 0};
string t;
char s[N][N];
deque <pii> q;
bool st1[N][N], st2[N][N];
pii v;
void solve(){
cin >> n >> m;
forn (i, 1, max (n, m)){
s[i][0] = s[0][i] = s[n + 1][i] = s[i][m + 1] = '.';
}
forn (i, 1, n){
cin >> t;
forn (j, 1, m){
s[i][j] = t[j - 1];
}
}
q.push_back ({1, 1});
d[1][1] = 1;
while (sz(q)){
// for (pii p: q) cout << p.F << " " << p.S << " ";
// cout << endl;
v = q[0];
q.pop_front();
forn (i, 0, 3){
x = v.F + dx[i];
y = v.S + dy[i];
if (s[x][y] != '.' && !d[x][y]){
if (s[x][y] == s[v.F][v.S]){
d[x][y] = d[v.F][v.S];
q.push_front ({x, y});
}
else{
d[x][y] = d[v.F][v.S] + 1;
q.push_back ({x, y});
ans = max (ans, d[x][y]);
}
}
}
}
// forn (i, 1, n){
// forn (j, 1, m){
// cout << d[i][j];
// }
// cout << endl;
// }
cout << ans << endl;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
// cin >> t1;
t1 = 1;
while (t1 --){
solve();
}
return 0;
}
/*
5
0.50 0.29 0.49 0.95 0.66
2 3
0 3
3 4
2 1
5
0.50 0.29 0.49 0.95 0.83
2 3
0 3
3 4
2 1
1
4 0.66
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
6228 KB |
Output is correct |
2 |
Correct |
1 ms |
468 KB |
Output is correct |
3 |
Correct |
1 ms |
736 KB |
Output is correct |
4 |
Correct |
8 ms |
5716 KB |
Output is correct |
5 |
Correct |
3 ms |
3232 KB |
Output is correct |
6 |
Correct |
1 ms |
468 KB |
Output is correct |
7 |
Correct |
1 ms |
732 KB |
Output is correct |
8 |
Correct |
1 ms |
852 KB |
Output is correct |
9 |
Correct |
2 ms |
1108 KB |
Output is correct |
10 |
Correct |
4 ms |
2644 KB |
Output is correct |
11 |
Correct |
3 ms |
2260 KB |
Output is correct |
12 |
Correct |
7 ms |
3412 KB |
Output is correct |
13 |
Correct |
4 ms |
3156 KB |
Output is correct |
14 |
Correct |
5 ms |
3160 KB |
Output is correct |
15 |
Correct |
10 ms |
5888 KB |
Output is correct |
16 |
Correct |
11 ms |
6228 KB |
Output is correct |
17 |
Correct |
9 ms |
5992 KB |
Output is correct |
18 |
Correct |
9 ms |
5716 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
31024 KB |
Output is correct |
2 |
Correct |
40 ms |
16776 KB |
Output is correct |
3 |
Correct |
198 ms |
75760 KB |
Output is correct |
4 |
Correct |
78 ms |
43348 KB |
Output is correct |
5 |
Correct |
168 ms |
62424 KB |
Output is correct |
6 |
Correct |
728 ms |
170524 KB |
Output is correct |
7 |
Correct |
20 ms |
32468 KB |
Output is correct |
8 |
Correct |
20 ms |
31084 KB |
Output is correct |
9 |
Correct |
7 ms |
15956 KB |
Output is correct |
10 |
Correct |
6 ms |
16084 KB |
Output is correct |
11 |
Correct |
17 ms |
31828 KB |
Output is correct |
12 |
Correct |
2 ms |
1620 KB |
Output is correct |
13 |
Correct |
50 ms |
16776 KB |
Output is correct |
14 |
Correct |
27 ms |
11728 KB |
Output is correct |
15 |
Correct |
29 ms |
16016 KB |
Output is correct |
16 |
Correct |
26 ms |
11348 KB |
Output is correct |
17 |
Correct |
96 ms |
32320 KB |
Output is correct |
18 |
Correct |
93 ms |
47468 KB |
Output is correct |
19 |
Correct |
77 ms |
43256 KB |
Output is correct |
20 |
Correct |
52 ms |
27724 KB |
Output is correct |
21 |
Correct |
117 ms |
53936 KB |
Output is correct |
22 |
Correct |
155 ms |
62420 KB |
Output is correct |
23 |
Correct |
172 ms |
52316 KB |
Output is correct |
24 |
Correct |
120 ms |
52756 KB |
Output is correct |
25 |
Correct |
497 ms |
141664 KB |
Output is correct |
26 |
Incorrect |
568 ms |
186124 KB |
Output isn't correct |
27 |
Correct |
656 ms |
175556 KB |
Output is correct |
28 |
Correct |
636 ms |
170512 KB |
Output is correct |
29 |
Correct |
754 ms |
168224 KB |
Output is correct |
30 |
Correct |
787 ms |
171676 KB |
Output is correct |
31 |
Correct |
621 ms |
106404 KB |
Output is correct |
32 |
Correct |
719 ms |
167224 KB |
Output is correct |