#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize ("Ofast")
#define all(x) x.begin() , x.end()
#define sze(x) (ll)(x.size())
#define mp(x , y) make_pair(x , y)
#define wall cout<<"--------------------------------------\n";
typedef long long int ll;
typedef pair<ll , ll> pll;
typedef pair<int , int> pii;
typedef double db;
typedef pair<pll , ll> plll;
typedef pair<int , pii> piii;
typedef pair<pll , pll> pllll;
const ll maxn = 4e3 + 17 , maxv = 16e6 + 17 , md = 1e9 + 7 , inf = 2e16;
int n , m;
vector<int> adj , f , g;
char a[maxn][maxn];
bool mark[maxv];
void bruh(ll v , bool t){
int i = v / m , j = v % m;
adj.clear();
if(i > 0){
if(a[i - 1][j] != '.'){
if((a[i - 1][j] != a[0][0]) == t) adj.push_back(v - m);
}
}
if(j > 0){
if(a[i][j - 1] != '.'){
if((a[i][j - 1] != a[0][0]) == t) adj.push_back(v - 1);
}
}
if(i < n - 1){
if(a[i + 1][j] != '.'){
if((a[i + 1][j] != a[0][0]) == t) adj.push_back(v + m);
}
}
if(j < m - 1){
if(a[i][j + 1] != '.'){
if((a[i][j + 1] != a[0][0]) == t) adj.push_back(v + 1);
}
}
return;
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin>>n>>m;
for(int i = 0 ; i < n ; i++){
for(int j = 0 ; j < m ; j++){
cin>>a[i][j];
}
}
for(int i = 0 ; i < n ; i++){
for(int j = 0 ; j < m ; j++){
int v = i * m + j;
}
}
int lm = n * m - 1;
mark[0] = mark[lm] = true;
f.push_back(0); f.push_back(lm);
g.push_back(0); g.push_back(lm);
int ans;
for(int j = 0 ; ; j++){
if(f.empty()){
ans = j - 1;
break;
}
int x = 0;
while(x < sze(f)){
int v = f[x++];
bruh(v , j & 1);
for(auto i : adj){
if(mark[i]) continue;
mark[i] = true;
f.push_back(i);
g.push_back(i);
}
}
f = g;
g.clear();
}
cout<<ans<<'\n';
return 0;
}
Compilation message
tracks.cpp: In function 'int main()':
tracks.cpp:63:8: warning: unused variable 'v' [-Wunused-variable]
63 | int v = i * m + j;
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
2772 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
468 KB |
Output is correct |
4 |
Correct |
16 ms |
3532 KB |
Output is correct |
5 |
Correct |
4 ms |
1492 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
468 KB |
Output is correct |
8 |
Correct |
1 ms |
596 KB |
Output is correct |
9 |
Correct |
1 ms |
724 KB |
Output is correct |
10 |
Correct |
4 ms |
1364 KB |
Output is correct |
11 |
Correct |
4 ms |
1620 KB |
Output is correct |
12 |
Correct |
9 ms |
1620 KB |
Output is correct |
13 |
Correct |
4 ms |
1492 KB |
Output is correct |
14 |
Correct |
4 ms |
1492 KB |
Output is correct |
15 |
Correct |
23 ms |
2804 KB |
Output is correct |
16 |
Correct |
25 ms |
2824 KB |
Output is correct |
17 |
Correct |
14 ms |
2536 KB |
Output is correct |
18 |
Correct |
13 ms |
3532 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
15316 KB |
Output is correct |
2 |
Correct |
99 ms |
6872 KB |
Output is correct |
3 |
Correct |
492 ms |
47552 KB |
Output is correct |
4 |
Correct |
128 ms |
11428 KB |
Output is correct |
5 |
Correct |
256 ms |
29804 KB |
Output is correct |
6 |
Correct |
1642 ms |
134820 KB |
Output is correct |
7 |
Correct |
8 ms |
16084 KB |
Output is correct |
8 |
Correct |
7 ms |
15444 KB |
Output is correct |
9 |
Correct |
4 ms |
468 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
8 ms |
15828 KB |
Output is correct |
12 |
Correct |
2 ms |
852 KB |
Output is correct |
13 |
Correct |
99 ms |
6924 KB |
Output is correct |
14 |
Correct |
49 ms |
4820 KB |
Output is correct |
15 |
Correct |
28 ms |
5192 KB |
Output is correct |
16 |
Correct |
44 ms |
2608 KB |
Output is correct |
17 |
Correct |
225 ms |
12344 KB |
Output is correct |
18 |
Correct |
108 ms |
12080 KB |
Output is correct |
19 |
Correct |
113 ms |
11468 KB |
Output is correct |
20 |
Correct |
109 ms |
10600 KB |
Output is correct |
21 |
Correct |
279 ms |
21716 KB |
Output is correct |
22 |
Correct |
268 ms |
29780 KB |
Output is correct |
23 |
Correct |
442 ms |
17940 KB |
Output is correct |
24 |
Correct |
248 ms |
30376 KB |
Output is correct |
25 |
Correct |
456 ms |
47404 KB |
Output is correct |
26 |
Correct |
775 ms |
136716 KB |
Output is correct |
27 |
Correct |
1104 ms |
151280 KB |
Output is correct |
28 |
Correct |
1566 ms |
134884 KB |
Output is correct |
29 |
Correct |
1896 ms |
133000 KB |
Output is correct |
30 |
Correct |
1436 ms |
160492 KB |
Output is correct |
31 |
Correct |
1343 ms |
34416 KB |
Output is correct |
32 |
Correct |
1098 ms |
146872 KB |
Output is correct |