#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pi;
#define mp make_pair
#define f first
#define s second
#define sz(x) (int)(x).size()
int xd[4] = {1, 0, -1, 0};
int yd[4] = {0, 1, 0, -1};
const int MOD = 1e9+7;
int grid[4005][4005];
int dist[4005][4005];
int ans = 1;
int main(){
int H, W;
cin >> H >> W;
for(int i = 1; i <= H; i++){
string s;
cin >> s;
for(int j = 0; j < W; j++){
if(s[j] == 'R'){
grid[i][j+1] = 1;
}
else if(s[j] == 'F'){
grid[i][j+1] = 2;
}
}
}
for(int i = 1; i <= H; i++){
for(int j = 1; j <= W; j++){
dist[i][j] = MOD;
}
}
queue<pi> q; //have ans value
queue<pi> nq;
dist[1][1] = 1;
q.push(mp(1, 1));
while(sz(q)){
pi co = q.front();
q.pop();
//cout << co.f << " " << co.s << "\n";
for(int d = 0; d < 4; d++){
int x = co.f+xd[d];
int y = co.s+yd[d];
if(grid[x][y] == 0) continue;
if(dist[x][y] != MOD) continue;
//cout << "x y: " << x << " " << y << "\n";
if(grid[x][y] == grid[co.f][co.s]){
dist[x][y] = ans;
q.push(mp(x, y));
}
else{
dist[x][y] = ans+1;
nq.push(mp(x, y));
}
}
if(sz(q) == 0){
if(sz(nq) == 0) break;
swap(nq, q);
//cout << "AD" << "\n";
ans++;
}
}
cout << ans << "\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
6380 KB |
Output is correct |
| 2 |
Correct |
1 ms |
512 KB |
Output is correct |
| 3 |
Correct |
1 ms |
748 KB |
Output is correct |
| 4 |
Correct |
13 ms |
5740 KB |
Output is correct |
| 5 |
Correct |
6 ms |
3308 KB |
Output is correct |
| 6 |
Correct |
1 ms |
492 KB |
Output is correct |
| 7 |
Correct |
1 ms |
748 KB |
Output is correct |
| 8 |
Correct |
1 ms |
896 KB |
Output is correct |
| 9 |
Correct |
1 ms |
1260 KB |
Output is correct |
| 10 |
Correct |
5 ms |
2796 KB |
Output is correct |
| 11 |
Correct |
4 ms |
2284 KB |
Output is correct |
| 12 |
Correct |
9 ms |
3436 KB |
Output is correct |
| 13 |
Correct |
5 ms |
3308 KB |
Output is correct |
| 14 |
Correct |
6 ms |
3308 KB |
Output is correct |
| 15 |
Correct |
19 ms |
6380 KB |
Output is correct |
| 16 |
Correct |
22 ms |
6396 KB |
Output is correct |
| 17 |
Correct |
21 ms |
6252 KB |
Output is correct |
| 18 |
Correct |
13 ms |
5760 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
31468 KB |
Output is correct |
| 2 |
Correct |
97 ms |
21356 KB |
Output is correct |
| 3 |
Correct |
631 ms |
120556 KB |
Output is correct |
| 4 |
Correct |
171 ms |
47540 KB |
Output is correct |
| 5 |
Correct |
372 ms |
88816 KB |
Output is correct |
| 6 |
Correct |
1715 ms |
151520 KB |
Output is correct |
| 7 |
Correct |
19 ms |
32876 KB |
Output is correct |
| 8 |
Correct |
18 ms |
31468 KB |
Output is correct |
| 9 |
Correct |
4 ms |
876 KB |
Output is correct |
| 10 |
Correct |
2 ms |
620 KB |
Output is correct |
| 11 |
Correct |
19 ms |
32236 KB |
Output is correct |
| 12 |
Correct |
2 ms |
1772 KB |
Output is correct |
| 13 |
Correct |
96 ms |
21440 KB |
Output is correct |
| 14 |
Correct |
53 ms |
14060 KB |
Output is correct |
| 15 |
Correct |
52 ms |
17132 KB |
Output is correct |
| 16 |
Correct |
39 ms |
8300 KB |
Output is correct |
| 17 |
Correct |
245 ms |
44908 KB |
Output is correct |
| 18 |
Correct |
190 ms |
51564 KB |
Output is correct |
| 19 |
Correct |
172 ms |
47468 KB |
Output is correct |
| 20 |
Correct |
139 ms |
39276 KB |
Output is correct |
| 21 |
Correct |
352 ms |
89068 KB |
Output is correct |
| 22 |
Correct |
373 ms |
88684 KB |
Output is correct |
| 23 |
Correct |
479 ms |
73324 KB |
Output is correct |
| 24 |
Correct |
350 ms |
85760 KB |
Output is correct |
| 25 |
Correct |
835 ms |
141420 KB |
Output is correct |
| 26 |
Correct |
987 ms |
122092 KB |
Output is correct |
| 27 |
Correct |
1321 ms |
143144 KB |
Output is correct |
| 28 |
Correct |
1670 ms |
151552 KB |
Output is correct |
| 29 |
Correct |
1602 ms |
150244 KB |
Output is correct |
| 30 |
Correct |
1530 ms |
146428 KB |
Output is correct |
| 31 |
Correct |
1168 ms |
111388 KB |
Output is correct |
| 32 |
Correct |
1207 ms |
142316 KB |
Output is correct |
