#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mp(x, y) (x << 13)+y
#define pb push_back
#define x first
#define y second
#define pii pair<int, int>
#define p3i pair<pii, int>
#define pll pair<ll, ll>
#define p3l pair<pll, ll>
#define lseg L, (L+R)/2, N*2+1
#define rseg (L+R)/2+1, R, N*2+2
#define ub upper_bound
#define lb lower_bound
#define pq priority_queue
#define MN 1000000007
#define fox(k, x) for (int k=0; k<x; ++k)
#define fox1(k, x) for (int k=1; k<=x; ++k)
#define foxr(k, x) for (int k=x-1; k>=0; --k)
#define fox1r(k, x) for (int k=x; k>0; --k)
#define ms multiset
#define flood(x) memset(x, 0x3f3f3f3f, sizeof x)
#define drain(x) memset(x, 0, sizeof x)
int n, m, X, Y, ans;
char g[4005][4005];
bool u[4005][4005], t;
queue<int> q[2];
void bfs(){
//cout << "*";
q[0].push(mp(1, 1));
for (ans=0; !q[t].empty(); ans++){
//cout << "*";
while(!q[t].empty()){
//cout << "*";
X=q[t].front() >> 13; Y=q[t].front() &((1 << 13)-1); q[t].pop();
if (u[X][Y]) continue;
u[X][Y]=1;
//cout << X << ' ' << Y << ' ' << g[X][Y]<< endl;
if (!(X+1>n || u[X+1][Y]))
q[(g[X+1][Y]!=g[X][Y]) != t].push(mp(X+1, Y));
if (!(X-1<1 || u[X-1][Y]))
q[(g[X-1][Y]!=g[X][Y]) != t].push(mp(X-1, Y));
if (!(Y+1>m || u[X][Y+1]))
q[(g[X][Y+1]!=g[X][Y]) != t].push(mp(X, Y+1));
if (!(Y-1<1 || u[X][Y-1]))
q[(g[X][Y-1]!=g[X][Y]) != t].push(mp(X, Y-1));
}
t=!t;
}
}
int main(){
scanf("%i%i", &n, &m);
fox1(l, n){
fox1(l2, m){
scanf(" %c", &g[l][l2]);
u[l][l2]=(g[l][l2]=='.');
}
}
bfs();
cout << ans << endl;
return 0;
}
Compilation message
tracks.cpp: In function 'void bfs()':
tracks.cpp:42:51: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
q[(g[X+1][Y]!=g[X][Y]) != t].push(mp(X+1, Y));
^
tracks.cpp:4:19: note: in definition of macro 'mp'
#define mp(x, y) (x << 13)+y
^
tracks.cpp:44:51: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
q[(g[X-1][Y]!=g[X][Y]) != t].push(mp(X-1, Y));
^
tracks.cpp:4:19: note: in definition of macro 'mp'
#define mp(x, y) (x << 13)+y
^
tracks.cpp: In function 'int main()':
tracks.cpp:54:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%i%i", &n, &m);
^
tracks.cpp:57:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf(" %c", &g[l][l2]);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
33480 KB |
Output is correct |
| 2 |
Correct |
0 ms |
33348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
33348 KB |
Output is correct |
| 4 |
Correct |
16 ms |
33480 KB |
Output is correct |
| 5 |
Correct |
6 ms |
33348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
33348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
33348 KB |
Output is correct |
| 8 |
Correct |
0 ms |
33348 KB |
Output is correct |
| 9 |
Correct |
0 ms |
33348 KB |
Output is correct |
| 10 |
Correct |
9 ms |
33348 KB |
Output is correct |
| 11 |
Correct |
6 ms |
33348 KB |
Output is correct |
| 12 |
Correct |
16 ms |
33348 KB |
Output is correct |
| 13 |
Correct |
6 ms |
33348 KB |
Output is correct |
| 14 |
Correct |
6 ms |
33348 KB |
Output is correct |
| 15 |
Correct |
23 ms |
33348 KB |
Output is correct |
| 16 |
Correct |
33 ms |
33480 KB |
Output is correct |
| 17 |
Correct |
19 ms |
33348 KB |
Output is correct |
| 18 |
Correct |
19 ms |
33480 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
33348 KB |
Output is correct |
| 2 |
Correct |
139 ms |
33348 KB |
Output is correct |
| 3 |
Correct |
1116 ms |
33348 KB |
Output is correct |
| 4 |
Correct |
299 ms |
33348 KB |
Output is correct |
| 5 |
Correct |
696 ms |
33348 KB |
Output is correct |
| 6 |
Execution timed out |
2000 ms |
42208 KB |
Execution timed out |
| 7 |
Correct |
3 ms |
33348 KB |
Output is correct |
| 8 |
Correct |
3 ms |
33348 KB |
Output is correct |
| 9 |
Correct |
0 ms |
33348 KB |
Output is correct |
| 10 |
Correct |
0 ms |
33348 KB |
Output is correct |
| 11 |
Correct |
0 ms |
33348 KB |
Output is correct |
| 12 |
Correct |
3 ms |
33348 KB |
Output is correct |
| 13 |
Correct |
129 ms |
33348 KB |
Output is correct |
| 14 |
Correct |
93 ms |
33348 KB |
Output is correct |
| 15 |
Correct |
79 ms |
33348 KB |
Output is correct |
| 16 |
Correct |
69 ms |
33348 KB |
Output is correct |
| 17 |
Correct |
373 ms |
33348 KB |
Output is correct |
| 18 |
Correct |
319 ms |
33348 KB |
Output is correct |
| 19 |
Correct |
326 ms |
33348 KB |
Output is correct |
| 20 |
Correct |
266 ms |
33348 KB |
Output is correct |
| 21 |
Correct |
633 ms |
33348 KB |
Output is correct |
| 22 |
Correct |
633 ms |
33348 KB |
Output is correct |
| 23 |
Correct |
713 ms |
33348 KB |
Output is correct |
| 24 |
Correct |
699 ms |
33348 KB |
Output is correct |
| 25 |
Correct |
1279 ms |
33348 KB |
Output is correct |
| 26 |
Execution timed out |
2000 ms |
33348 KB |
Execution timed out |
| 27 |
Execution timed out |
2000 ms |
35088 KB |
Execution timed out |
| 28 |
Execution timed out |
2000 ms |
42208 KB |
Execution timed out |
| 29 |
Execution timed out |
2000 ms |
40400 KB |
Execution timed out |
| 30 |
Correct |
1843 ms |
40228 KB |
Output is correct |
| 31 |
Correct |
1569 ms |
33744 KB |
Output is correct |
| 32 |
Execution timed out |
2000 ms |
34400 KB |
Execution timed out |
