#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;
vector <pii> g[N][N];
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, n){
cin >> t;
forn (j, 1, m){
s[i][j] = t[j - 1];
if (i > 1 && s[i][j] != '.' && s[i - 1][j] != '.') {
g[i][j].pb ({i - 1, j});
g[i - 1][j].pb ({i, j});
if (s[i][j] == s[i - 1][j]) st2[i][j] = 0;
else st2[i][j] = 1;
}
if (j > 1 && s[i][j] != '.' && s[i][j - 1] != '.') {
g[i][j].pb ({i, j - 1});
g[i][j - 1].pb ({i, j});
if (s[i][j] == s[i][j - 1]) st1[i][j] = 0;
else st1[i][j] = 1;
}
}
}
q.push_back ({1, 1});
d[1][1] = 1;
while (q.size()){
v = q[0];
q.pop_front();
for (pii to: g[v.F][v.S]){
if (!d[to.F][to.S]){
d[to.F][to.S] = d[v.F][v.S];
if (v.F == to.F && !st1[v.F][max (v.S, to.S)] || v.S == to.S && !st2[max (v.F, to.F)][v.S]) q.push_front (to);
else {
q.push_back (to);
d[to.F][to.S] ++;
}
ans = max (ans, d[to.F][to.S]);
}
}
}
// 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
*/
Compilation message
tracks.cpp: In function 'void solve()':
tracks.cpp:58:21: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
58 | if (v.F == to.F && !st1[v.F][max (v.S, to.S)] || v.S == to.S && !st2[max (v.F, to.F)][v.S]) q.push_front (to);
| ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
223 ms |
399340 KB |
Output is correct |
| 2 |
Correct |
168 ms |
378700 KB |
Output is correct |
| 3 |
Correct |
170 ms |
379320 KB |
Output is correct |
| 4 |
Correct |
204 ms |
394944 KB |
Output is correct |
| 5 |
Correct |
179 ms |
384508 KB |
Output is correct |
| 6 |
Correct |
174 ms |
378764 KB |
Output is correct |
| 7 |
Correct |
180 ms |
379328 KB |
Output is correct |
| 8 |
Correct |
179 ms |
379644 KB |
Output is correct |
| 9 |
Correct |
174 ms |
380108 KB |
Output is correct |
| 10 |
Correct |
177 ms |
383940 KB |
Output is correct |
| 11 |
Correct |
183 ms |
383948 KB |
Output is correct |
| 12 |
Correct |
192 ms |
387704 KB |
Output is correct |
| 13 |
Correct |
181 ms |
384440 KB |
Output is correct |
| 14 |
Correct |
182 ms |
384364 KB |
Output is correct |
| 15 |
Correct |
215 ms |
396400 KB |
Output is correct |
| 16 |
Correct |
221 ms |
399488 KB |
Output is correct |
| 17 |
Correct |
199 ms |
392508 KB |
Output is correct |
| 18 |
Correct |
305 ms |
394996 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
204 ms |
429092 KB |
Output is correct |
| 2 |
Correct |
313 ms |
434728 KB |
Output is correct |
| 3 |
Correct |
869 ms |
653492 KB |
Output is correct |
| 4 |
Correct |
406 ms |
459952 KB |
Output is correct |
| 5 |
Correct |
679 ms |
612520 KB |
Output is correct |
| 6 |
Runtime error |
1646 ms |
1048576 KB |
Execution killed with signal 9 |
| 7 |
Correct |
205 ms |
431180 KB |
Output is correct |
| 8 |
Correct |
207 ms |
429028 KB |
Output is correct |
| 9 |
Correct |
189 ms |
380400 KB |
Output is correct |
| 10 |
Correct |
181 ms |
379132 KB |
Output is correct |
| 11 |
Correct |
201 ms |
426904 KB |
Output is correct |
| 12 |
Correct |
181 ms |
381000 KB |
Output is correct |
| 13 |
Correct |
322 ms |
434504 KB |
Output is correct |
| 14 |
Correct |
262 ms |
414356 KB |
Output is correct |
| 15 |
Correct |
255 ms |
408316 KB |
Output is correct |
| 16 |
Correct |
248 ms |
404392 KB |
Output is correct |
| 17 |
Correct |
514 ms |
501720 KB |
Output is correct |
| 18 |
Correct |
451 ms |
472168 KB |
Output is correct |
| 19 |
Correct |
378 ms |
460172 KB |
Output is correct |
| 20 |
Correct |
337 ms |
458320 KB |
Output is correct |
| 21 |
Correct |
579 ms |
552764 KB |
Output is correct |
| 22 |
Correct |
685 ms |
608532 KB |
Output is correct |
| 23 |
Correct |
860 ms |
593956 KB |
Output is correct |
| 24 |
Correct |
561 ms |
549276 KB |
Output is correct |
| 25 |
Correct |
1736 ms |
683316 KB |
Output is correct |
| 26 |
Runtime error |
1547 ms |
1048576 KB |
Execution killed with signal 9 |
| 27 |
Runtime error |
1681 ms |
1048576 KB |
Execution killed with signal 9 |
| 28 |
Runtime error |
1673 ms |
1048576 KB |
Execution killed with signal 9 |
| 29 |
Runtime error |
1594 ms |
1048576 KB |
Execution killed with signal 9 |
| 30 |
Runtime error |
1639 ms |
1048576 KB |
Execution killed with signal 9 |
| 31 |
Execution timed out |
2145 ms |
959400 KB |
Time limit exceeded |
| 32 |
Runtime error |
1620 ms |
1048576 KB |
Execution killed with signal 9 |
