#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
using pii = pair<int, int>;
const int MXN = 4005;
int n, m;
int A[MXN][MXN];
int dirI[] = {0, 0, -1, 1};
int dirJ[] = {-1, 1, 0, 0};
bool inbounds(int i, int j)
{
return i >= 0 && i < n && j >= 0 && j < m;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
char c; cin >> c;
if(c == '.') A[i][j] = -1;
else if(c == 'F') A[i][j] = 0;
else A[i][j] = 1;
}
}
queue<pii> Q[2];
int which = A[0][0];
A[0][0] = -1;
Q[which].push({0, 0});
int cnt = 0;
do {
// for(int i = 0; i < n; i++) {
// for(int j = 0; j < m; j++) {
// cerr << setw(2) << A[i][j] << " ";
// }
// cerr << "\n";
// }
// cerr << "\n";
while(!Q[which].empty()) {
int i = Q[which].front().F, j = Q[which].front().S;
Q[which].pop();
for(int k = 0; k < 4; k++) {
int ii = i + dirI[k], jj = j + dirJ[k];
if(inbounds(ii, jj)) {
if(A[ii][jj] == which) {
A[ii][jj] = -1;
Q[which].push({ii, jj});
}
else if(A[ii][jj] == 1-which) {
A[ii][jj] = -1;
Q[1-which].push({ii, jj});
}
}
}
}
which = 1-which;
cnt++;
} while(!Q[which].empty());
cout << cnt;
return 0;
}
/*
5 8
FFR.....
.FRRR...
.FFFFF..
..RRRFFR
.....FFF
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
3500 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
468 KB |
Output is correct |
4 |
Correct |
10 ms |
3208 KB |
Output is correct |
5 |
Correct |
3 ms |
1876 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
456 KB |
Output is correct |
8 |
Correct |
1 ms |
596 KB |
Output is correct |
9 |
Correct |
1 ms |
724 KB |
Output is correct |
10 |
Correct |
3 ms |
1620 KB |
Output is correct |
11 |
Correct |
3 ms |
1364 KB |
Output is correct |
12 |
Correct |
6 ms |
1880 KB |
Output is correct |
13 |
Correct |
3 ms |
1876 KB |
Output is correct |
14 |
Correct |
4 ms |
1876 KB |
Output is correct |
15 |
Correct |
12 ms |
3564 KB |
Output is correct |
16 |
Correct |
15 ms |
3508 KB |
Output is correct |
17 |
Correct |
11 ms |
3412 KB |
Output is correct |
18 |
Correct |
9 ms |
3152 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
15956 KB |
Output is correct |
2 |
Correct |
58 ms |
12792 KB |
Output is correct |
3 |
Correct |
384 ms |
64852 KB |
Output is correct |
4 |
Correct |
108 ms |
23828 KB |
Output is correct |
5 |
Correct |
220 ms |
48588 KB |
Output is correct |
6 |
Correct |
979 ms |
75000 KB |
Output is correct |
7 |
Correct |
8 ms |
16596 KB |
Output is correct |
8 |
Correct |
8 ms |
15956 KB |
Output is correct |
9 |
Correct |
3 ms |
596 KB |
Output is correct |
10 |
Correct |
2 ms |
468 KB |
Output is correct |
11 |
Correct |
10 ms |
16340 KB |
Output is correct |
12 |
Correct |
1 ms |
980 KB |
Output is correct |
13 |
Correct |
69 ms |
12704 KB |
Output is correct |
14 |
Correct |
30 ms |
8320 KB |
Output is correct |
15 |
Correct |
32 ms |
9176 KB |
Output is correct |
16 |
Correct |
24 ms |
5076 KB |
Output is correct |
17 |
Correct |
137 ms |
25500 KB |
Output is correct |
18 |
Correct |
143 ms |
25336 KB |
Output is correct |
19 |
Correct |
100 ms |
23844 KB |
Output is correct |
20 |
Correct |
83 ms |
22084 KB |
Output is correct |
21 |
Correct |
224 ms |
50072 KB |
Output is correct |
22 |
Correct |
233 ms |
48540 KB |
Output is correct |
23 |
Correct |
275 ms |
40824 KB |
Output is correct |
24 |
Correct |
238 ms |
49476 KB |
Output is correct |
25 |
Correct |
648 ms |
65052 KB |
Output is correct |
26 |
Correct |
503 ms |
56888 KB |
Output is correct |
27 |
Correct |
738 ms |
66328 KB |
Output is correct |
28 |
Correct |
986 ms |
74164 KB |
Output is correct |
29 |
Correct |
955 ms |
72640 KB |
Output is correct |
30 |
Correct |
811 ms |
70616 KB |
Output is correct |
31 |
Correct |
670 ms |
51424 KB |
Output is correct |
32 |
Correct |
668 ms |
63936 KB |
Output is correct |