#include <iostream>
#include <fstream>
#include <queue>
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)
{
deque< pair<int,int> > q;
q.push_back({L,C});
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
d[i][j]=n*m+1;
d[L][C]=0;
while(!q.empty())
{
li=q.front().first;ci=q.front().second;q.pop_front();
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-1]=='R'||s[lf][cf-1]=='F'))
{
dd=d[li][ci]+(s[li][ci-1]!=s[lf][cf-1]);
if(dd<d[lf][cf])
{
d[lf][cf]=dd;
if(dd=d[li][ci]) q.push_front({lf,cf});
else q.push_back({lf,cf});
}
}
}
}
}
int main()
{
// freopen("data.in","r",stdin);
ios_base::sync_with_stdio(false);
cin>>n>>m;getline(cin,s[0]);
for(i=1;i<=n;i++)
{
getline(cin,s[i]);
}
dij(1,1);
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
if(s[i][j-1]=='R'||s[i][j-1]=='F')
mx=max(mx,d[i][j]);
cout<<mx+1;
return 0;
}
Compilation message
tracks.cpp: In function 'void dij(int, int)':
tracks.cpp:35:32: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
if(dd=d[li][ci]) q.push_front({lf,cf});
~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2060 ms |
4736 KB |
Time limit exceeded |
| 2 |
Correct |
2 ms |
4736 KB |
Output is correct |
| 3 |
Correct |
5 ms |
4736 KB |
Output is correct |
| 4 |
Execution timed out |
2060 ms |
4736 KB |
Time limit exceeded |
| 5 |
Correct |
1215 ms |
4736 KB |
Output is correct |
| 6 |
Correct |
2 ms |
4736 KB |
Output is correct |
| 7 |
Correct |
5 ms |
4736 KB |
Output is correct |
| 8 |
Correct |
74 ms |
4736 KB |
Output is correct |
| 9 |
Correct |
11 ms |
4736 KB |
Output is correct |
| 10 |
Correct |
1371 ms |
4736 KB |
Output is correct |
| 11 |
Correct |
1632 ms |
4736 KB |
Output is correct |
| 12 |
Execution timed out |
2062 ms |
4736 KB |
Time limit exceeded |
| 13 |
Correct |
1248 ms |
4736 KB |
Output is correct |
| 14 |
Correct |
1141 ms |
4736 KB |
Output is correct |
| 15 |
Execution timed out |
2050 ms |
4736 KB |
Time limit exceeded |
| 16 |
Execution timed out |
2065 ms |
4836 KB |
Time limit exceeded |
| 17 |
Execution timed out |
2057 ms |
4836 KB |
Time limit exceeded |
| 18 |
Execution timed out |
2021 ms |
4836 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
16228 KB |
Output is correct |
| 2 |
Execution timed out |
2056 ms |
16228 KB |
Time limit exceeded |
| 3 |
Execution timed out |
2056 ms |
83880 KB |
Time limit exceeded |
| 4 |
Execution timed out |
2073 ms |
83880 KB |
Time limit exceeded |
| 5 |
Correct |
201 ms |
83880 KB |
Output is correct |
| 6 |
Execution timed out |
2040 ms |
146708 KB |
Time limit exceeded |
| 7 |
Correct |
20 ms |
146708 KB |
Output is correct |
| 8 |
Correct |
20 ms |
146708 KB |
Output is correct |
| 9 |
Execution timed out |
2062 ms |
146708 KB |
Time limit exceeded |
| 10 |
Correct |
4 ms |
146708 KB |
Output is correct |
| 11 |
Correct |
18 ms |
146708 KB |
Output is correct |
| 12 |
Correct |
4 ms |
146708 KB |
Output is correct |
| 13 |
Execution timed out |
2066 ms |
146708 KB |
Time limit exceeded |
| 14 |
Execution timed out |
2043 ms |
146708 KB |
Time limit exceeded |
| 15 |
Correct |
32 ms |
146708 KB |
Output is correct |
| 16 |
Execution timed out |
2052 ms |
146708 KB |
Time limit exceeded |
| 17 |
Execution timed out |
2068 ms |
146708 KB |
Time limit exceeded |
| 18 |
Correct |
181 ms |
146708 KB |
Output is correct |
| 19 |
Execution timed out |
2064 ms |
146708 KB |
Time limit exceeded |
| 20 |
Execution timed out |
2069 ms |
146708 KB |
Time limit exceeded |
| 21 |
Execution timed out |
2056 ms |
146708 KB |
Time limit exceeded |
| 22 |
Correct |
244 ms |
146708 KB |
Output is correct |
| 23 |
Execution timed out |
2058 ms |
146708 KB |
Time limit exceeded |
| 24 |
Correct |
209 ms |
146708 KB |
Output is correct |
| 25 |
Correct |
765 ms |
146708 KB |
Output is correct |
| 26 |
Correct |
1324 ms |
146708 KB |
Output is correct |
| 27 |
Execution timed out |
2053 ms |
146708 KB |
Time limit exceeded |
| 28 |
Execution timed out |
2068 ms |
146708 KB |
Time limit exceeded |
| 29 |
Execution timed out |
2061 ms |
146708 KB |
Time limit exceeded |
| 30 |
Execution timed out |
2050 ms |
146708 KB |
Time limit exceeded |
| 31 |
Execution timed out |
2086 ms |
146708 KB |
Time limit exceeded |
| 32 |
Execution timed out |
2071 ms |
146708 KB |
Time limit exceeded |
