#include <bits/stdc++.h>
using namespace std;
int h, w, total;
int meadow[4005][4005];
bool vis[4005][4005];
// vector<pair<int, int>> dir = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int main() {
cin >> h >> w;
char in;
for (int i = 1; i <= h; i++) {
for (int j = 1; j <= w; j++) {
cin >> in;
if (in == '.') {
meadow[i][j] = -1;
} else if (in == 'R') {
meadow[i][j] = 1;
total++;
}
else {
meadow[i][j] = 0;
total++;
}
}
}
// for (int i = 1; i <= h; i++) {
// for (int j = 1; j <= w; j++) {
// cout << meadow[i][j] << "\t";
// }
// cout << endl;
// }
int ans = 0;
while (true) {
queue<pair<int, int>> q;
memset(vis, 0, sizeof(vis));
q.push({1, 1});
vis[1][1] = 1;
int row, col, count = 1;
int top = meadow[1][1];
meadow[1][1] += 1;
meadow[1][1] %= 2;
ans++;
while (!q.empty()) {
row = q.front().first;
col = q.front().second;
q.pop();
for (int i = 0; i < 4; i++) {
if (row + dir[i][0] > 0 and row + dir[i][0] <= h and col + dir[i][1] > 0 and col + dir[i][1] <= w and !vis[row+dir[i][0]][col+dir[i][1]] and meadow[row+dir[i][0]][col+dir[i][1]] == top) {
q.push({row+dir[i][0], col+dir[i][1]});
meadow[row+dir[i][0]][col+dir[i][1]] += 1;
meadow[row+dir[i][0]][col+dir[i][1]] %= 2;
vis[row+dir[i][0]][col+dir[i][1]] = 1;
count++;
}
}
}
// for (int i = 1; i <= h; i++) {
// for (int j = 1; j <= w; j++) {
// cout << meadow[i][j] << "\t";
// }
// cout << endl;
// }
// cout << count << " " << total << endl;
// cout << endl;
// break;
if (count == total) {
cout << ans << endl;
return 0;
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
228 ms |
18876 KB |
Output is correct |
| 2 |
Correct |
133 ms |
16068 KB |
Output is correct |
| 3 |
Correct |
32 ms |
16084 KB |
Output is correct |
| 4 |
Correct |
39 ms |
18556 KB |
Output is correct |
| 5 |
Correct |
138 ms |
17452 KB |
Output is correct |
| 6 |
Correct |
122 ms |
15956 KB |
Output is correct |
| 7 |
Correct |
42 ms |
16084 KB |
Output is correct |
| 8 |
Correct |
14 ms |
16260 KB |
Output is correct |
| 9 |
Correct |
55 ms |
16424 KB |
Output is correct |
| 10 |
Correct |
178 ms |
17236 KB |
Output is correct |
| 11 |
Correct |
16 ms |
16956 KB |
Output is correct |
| 12 |
Correct |
95 ms |
17512 KB |
Output is correct |
| 13 |
Correct |
138 ms |
17448 KB |
Output is correct |
| 14 |
Correct |
164 ms |
17364 KB |
Output is correct |
| 15 |
Correct |
463 ms |
18964 KB |
Output is correct |
| 16 |
Correct |
177 ms |
18772 KB |
Output is correct |
| 17 |
Correct |
490 ms |
18824 KB |
Output is correct |
| 18 |
Correct |
29 ms |
18516 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2065 ms |
31492 KB |
Time limit exceeded |
| 2 |
Execution timed out |
2089 ms |
27212 KB |
Time limit exceeded |
| 3 |
Execution timed out |
2078 ms |
78632 KB |
Time limit exceeded |
| 4 |
Execution timed out |
2070 ms |
38188 KB |
Time limit exceeded |
| 5 |
Execution timed out |
2075 ms |
62972 KB |
Time limit exceeded |
| 6 |
Execution timed out |
2075 ms |
78720 KB |
Time limit exceeded |
| 7 |
Execution timed out |
2052 ms |
32212 KB |
Time limit exceeded |
| 8 |
Execution timed out |
2069 ms |
31444 KB |
Time limit exceeded |
| 9 |
Correct |
320 ms |
16216 KB |
Output is correct |
| 10 |
Execution timed out |
2062 ms |
16084 KB |
Time limit exceeded |
| 11 |
Execution timed out |
2060 ms |
31908 KB |
Time limit exceeded |
| 12 |
Execution timed out |
2057 ms |
16596 KB |
Time limit exceeded |
| 13 |
Execution timed out |
2063 ms |
27104 KB |
Time limit exceeded |
| 14 |
Execution timed out |
2086 ms |
23160 KB |
Time limit exceeded |
| 15 |
Execution timed out |
2074 ms |
23848 KB |
Time limit exceeded |
| 16 |
Execution timed out |
2029 ms |
20088 KB |
Time limit exceeded |
| 17 |
Execution timed out |
2043 ms |
39920 KB |
Time limit exceeded |
| 18 |
Execution timed out |
2052 ms |
39576 KB |
Time limit exceeded |
| 19 |
Execution timed out |
2060 ms |
38196 KB |
Time limit exceeded |
| 20 |
Execution timed out |
2067 ms |
36416 KB |
Time limit exceeded |
| 21 |
Execution timed out |
2068 ms |
64568 KB |
Time limit exceeded |
| 22 |
Execution timed out |
2045 ms |
63000 KB |
Time limit exceeded |
| 23 |
Execution timed out |
2061 ms |
55168 KB |
Time limit exceeded |
| 24 |
Execution timed out |
2093 ms |
64000 KB |
Time limit exceeded |
| 25 |
Execution timed out |
2081 ms |
78620 KB |
Time limit exceeded |
| 26 |
Correct |
770 ms |
70792 KB |
Output is correct |
| 27 |
Execution timed out |
2056 ms |
78712 KB |
Time limit exceeded |
| 28 |
Execution timed out |
2099 ms |
78708 KB |
Time limit exceeded |
| 29 |
Execution timed out |
2085 ms |
78708 KB |
Time limit exceeded |
| 30 |
Execution timed out |
2081 ms |
77448 KB |
Time limit exceeded |
| 31 |
Execution timed out |
2089 ms |
66168 KB |
Time limit exceeded |
| 32 |
Execution timed out |
2065 ms |
78640 KB |
Time limit exceeded |
