#include <iostream>
#include <fstream>
using namespace std;
const int nmax=4005;
int d[nmax][nmax];
pair<int,int> q[2][nmax*nmax];
string s[nmax];
int p[2],u[2];
bool E[nmax][nmax];
int use,mx,i,j,dd,n,m,li,ci,lf,cf,di;
int d1[]={-1,0,1,0};
int d2[]={0,-1,0,1};
void dij(int L,int C)
{
p[0]=p[1]=1;
u[0]=u[1]=0;
q[0][++u[0]]={L,C};use=0;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
d[i][j]=n*m+1,E[i][j]=0;
d[L][C]=0;
for(i=0;i<=n*m;i++)
{
if(p[use]>u[use])
return;
mx=max(mx,i);
for(p[use]=1;p[use]<=u[use];p[use]++)
{
li=q[use][p[use]].first;ci=q[use][p[use]].second;
if(!E[li][ci])
for(di=0;di<4;di++)
{
lf=li+d1[di];cf=ci+d2[di];
if(lf>=1&&cf>=1&&lf<=n&&cf<=m&&(s[lf][cf]=='R'||s[lf][cf]=='F'))
{
dd=d[li][ci]+(s[li][ci]!=s[lf][cf]);
if(dd<d[lf][cf])
{
d[lf][cf]=dd;
q[(dd&1)][++u[(dd&1)]]={lf,cf};
}
}
}
E[li][ci]=1;
}
p[use]=1;u[use]=0;
use=1-use;
}
}
int main()
{
// freopen("data.in","r",stdin);
cin>>n>>m;getline(cin,s[0]);
for(i=1;i<=n;i++)
{
getline(cin,s[i]);
s[i]=" "+s[i];
}
dij(1,1);
dij(n,m);
cout<<mx+1;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
62 ms |
6016 KB |
Output is correct |
| 2 |
Correct |
4 ms |
6016 KB |
Output is correct |
| 3 |
Correct |
4 ms |
6016 KB |
Output is correct |
| 4 |
Correct |
43 ms |
6752 KB |
Output is correct |
| 5 |
Correct |
16 ms |
6752 KB |
Output is correct |
| 6 |
Correct |
4 ms |
6752 KB |
Output is correct |
| 7 |
Correct |
3 ms |
6752 KB |
Output is correct |
| 8 |
Correct |
5 ms |
6752 KB |
Output is correct |
| 9 |
Correct |
5 ms |
6752 KB |
Output is correct |
| 10 |
Correct |
14 ms |
6752 KB |
Output is correct |
| 11 |
Correct |
12 ms |
6752 KB |
Output is correct |
| 12 |
Correct |
23 ms |
6752 KB |
Output is correct |
| 13 |
Correct |
13 ms |
6752 KB |
Output is correct |
| 14 |
Correct |
13 ms |
6752 KB |
Output is correct |
| 15 |
Correct |
75 ms |
7124 KB |
Output is correct |
| 16 |
Correct |
81 ms |
7368 KB |
Output is correct |
| 17 |
Correct |
45 ms |
7368 KB |
Output is correct |
| 18 |
Correct |
40 ms |
8096 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
36 ms |
33080 KB |
Output is correct |
| 2 |
Correct |
251 ms |
33080 KB |
Output is correct |
| 3 |
Correct |
1316 ms |
104028 KB |
Output is correct |
| 4 |
Correct |
362 ms |
104028 KB |
Output is correct |
| 5 |
Correct |
984 ms |
104028 KB |
Output is correct |
| 6 |
Execution timed out |
2040 ms |
155636 KB |
Time limit exceeded |
| 7 |
Correct |
39 ms |
155636 KB |
Output is correct |
| 8 |
Correct |
40 ms |
155636 KB |
Output is correct |
| 9 |
Correct |
13 ms |
155636 KB |
Output is correct |
| 10 |
Correct |
8 ms |
155636 KB |
Output is correct |
| 11 |
Correct |
34 ms |
155636 KB |
Output is correct |
| 12 |
Correct |
5 ms |
155636 KB |
Output is correct |
| 13 |
Correct |
309 ms |
155636 KB |
Output is correct |
| 14 |
Correct |
135 ms |
155636 KB |
Output is correct |
| 15 |
Correct |
185 ms |
155636 KB |
Output is correct |
| 16 |
Correct |
101 ms |
155636 KB |
Output is correct |
| 17 |
Correct |
612 ms |
155636 KB |
Output is correct |
| 18 |
Correct |
493 ms |
155636 KB |
Output is correct |
| 19 |
Correct |
423 ms |
155636 KB |
Output is correct |
| 20 |
Correct |
358 ms |
155636 KB |
Output is correct |
| 21 |
Correct |
997 ms |
155636 KB |
Output is correct |
| 22 |
Correct |
887 ms |
155636 KB |
Output is correct |
| 23 |
Correct |
1250 ms |
155636 KB |
Output is correct |
| 24 |
Correct |
735 ms |
155636 KB |
Output is correct |
| 25 |
Execution timed out |
2045 ms |
155636 KB |
Time limit exceeded |
| 26 |
Execution timed out |
2033 ms |
182748 KB |
Time limit exceeded |
| 27 |
Execution timed out |
2089 ms |
198288 KB |
Time limit exceeded |
| 28 |
Execution timed out |
2036 ms |
198288 KB |
Time limit exceeded |
| 29 |
Execution timed out |
2097 ms |
198288 KB |
Time limit exceeded |
| 30 |
Execution timed out |
2033 ms |
198288 KB |
Time limit exceeded |
| 31 |
Execution timed out |
2073 ms |
198288 KB |
Time limit exceeded |
| 32 |
Execution timed out |
2097 ms |
204252 KB |
Time limit exceeded |
