#include<iostream>
#include<queue>
#include<string>
using namespace std;
typedef pair<int,int>ii;
queue<ii>q[2];
int R,C,K=0,res=0;
bool s;
string d[4000];
const string fr="FR";
int main(){
cin>>R>>C;
q[0]=queue<ii>();
q[1]=queue<ii>();
for(int i=0;i<R;++i){
cin>>ws;
cin>>d[i];
for(int j=0;j<C;++j)if(d[i][j]=='.')++K;
}
s=d[0][0]==fr[1];
d[0][0]='.';
q[s].push({0,0});
while(K<R*C){
//cout<<"---"<<K<<endl;
//cout<<q[0].size()<<' '<<q[1].size()<<endl;
++res;
q[!s]=queue<ii>();
while(!q[s].empty()){
++K;
//cout<<"IT"<<endl;
ii rw=q[s].front();
int x=rw.first,y=rw.second;
//cout<<q[s].size()<<' '<<x<<' '<<y<<endl;
q[s].pop();
if(0<x&&d[x-1][y]!='.'){
q[d[x-1][y]==fr[1]].push({x-1,y});
d[x-1][y]='.';
}
if(x<R-1&&d[x+1][y]!='.'){
q[d[x+1][y]==fr[1]].push({x+1,y});
d[x+1][y]='.';
}
if(0<y&&d[x][y-1]!='.'){
q[d[x][y-1]==fr[1]].push({x,y-1});
d[x][y-1]='.';
}
if(y<C-1&&d[x][y+1]!='.'){
q[d[x][y+1]==fr[1]].push({x,y+1});
d[x][y+1]='.';
}
}
s=!s;
}
cout<<res<<'\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
888 KB |
Output is correct |
| 2 |
Correct |
2 ms |
888 KB |
Output is correct |
| 3 |
Correct |
2 ms |
888 KB |
Output is correct |
| 4 |
Correct |
11 ms |
888 KB |
Output is correct |
| 5 |
Correct |
6 ms |
888 KB |
Output is correct |
| 6 |
Correct |
2 ms |
888 KB |
Output is correct |
| 7 |
Correct |
2 ms |
888 KB |
Output is correct |
| 8 |
Correct |
2 ms |
888 KB |
Output is correct |
| 9 |
Correct |
3 ms |
888 KB |
Output is correct |
| 10 |
Correct |
5 ms |
888 KB |
Output is correct |
| 11 |
Correct |
5 ms |
888 KB |
Output is correct |
| 12 |
Correct |
8 ms |
888 KB |
Output is correct |
| 13 |
Correct |
6 ms |
888 KB |
Output is correct |
| 14 |
Correct |
6 ms |
888 KB |
Output is correct |
| 15 |
Correct |
16 ms |
1124 KB |
Output is correct |
| 16 |
Correct |
18 ms |
1248 KB |
Output is correct |
| 17 |
Correct |
15 ms |
1248 KB |
Output is correct |
| 18 |
Correct |
14 ms |
1248 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
1248 KB |
Output is correct |
| 2 |
Correct |
80 ms |
3816 KB |
Output is correct |
| 3 |
Correct |
778 ms |
45256 KB |
Output is correct |
| 4 |
Correct |
170 ms |
45256 KB |
Output is correct |
| 5 |
Correct |
873 ms |
45256 KB |
Output is correct |
| 6 |
Correct |
1147 ms |
78544 KB |
Output is correct |
| 7 |
Correct |
5 ms |
78544 KB |
Output is correct |
| 8 |
Correct |
6 ms |
78544 KB |
Output is correct |
| 9 |
Correct |
5 ms |
78544 KB |
Output is correct |
| 10 |
Correct |
3 ms |
78544 KB |
Output is correct |
| 11 |
Correct |
5 ms |
78544 KB |
Output is correct |
| 12 |
Correct |
4 ms |
78544 KB |
Output is correct |
| 13 |
Correct |
79 ms |
78544 KB |
Output is correct |
| 14 |
Correct |
47 ms |
78544 KB |
Output is correct |
| 15 |
Correct |
64 ms |
78544 KB |
Output is correct |
| 16 |
Correct |
37 ms |
78544 KB |
Output is correct |
| 17 |
Correct |
215 ms |
78544 KB |
Output is correct |
| 18 |
Correct |
259 ms |
78544 KB |
Output is correct |
| 19 |
Correct |
168 ms |
78544 KB |
Output is correct |
| 20 |
Correct |
160 ms |
78544 KB |
Output is correct |
| 21 |
Correct |
462 ms |
78544 KB |
Output is correct |
| 22 |
Correct |
882 ms |
78544 KB |
Output is correct |
| 23 |
Correct |
416 ms |
80064 KB |
Output is correct |
| 24 |
Correct |
546 ms |
89660 KB |
Output is correct |
| 25 |
Correct |
1052 ms |
121396 KB |
Output is correct |
| 26 |
Correct |
776 ms |
121396 KB |
Output is correct |
| 27 |
Correct |
1051 ms |
138348 KB |
Output is correct |
| 28 |
Correct |
1179 ms |
146708 KB |
Output is correct |
| 29 |
Correct |
1153 ms |
146708 KB |
Output is correct |
| 30 |
Correct |
1064 ms |
146708 KB |
Output is correct |
| 31 |
Correct |
796 ms |
146708 KB |
Output is correct |
| 32 |
Correct |
977 ms |
146708 KB |
Output is correct |
