#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector,Ofast")
using namespace std;
typedef int ll;
typedef pair<ll,ll> pll;
#define X first
#define Y second
#define mp make_pair
#define REP(i,n) for(int i=0;i<n;i++)
const ll N=4e3;
char grid[N*N];
bitset<N*N> vis;
queue<ll> que;
vector<ll> nxt;
ll n,m,ans;
ll get(ll r,ll c){
return r*m+c;
}
ll dest(ll now,ll dir){
if(dir==0)return (now/m==0?-1:now-m);
if(dir==1)return (now%m==0?-1:now-1);
if(dir==2)return (now/m==n-1?-1:now+m);
if(dir==3)return (now%m==m-1?-1:now+1);
}
int main(){
//ios_base::sync_with_stdio(0);cin.tie(0);
cin>>n>>m;
REP(i,n)REP(j,m){
while(1){
grid[get(i,j)]=getchar();
if(grid[get(i,j)]==' '||grid[get(i,j)]=='\n')continue;
break;
}
}
que.push(get(0,0));vis[get(0,0)]=1;
que.push(get(n-1,m-1));vis[get(n-1,m-1)]=1;
for(char i=grid[get(0,0)];;i=(i=='F'?'R':'F')){
nxt.clear();
++ans;
while(!(que.empty())){
ll nd=que.front();que.pop();
for(int j=0;j<4;j++){
ll to=dest(nd,j);
if(to==-1||vis[to])continue;
if(grid[to]==i){
vis[to]=1;
que.push(to);
}else if(grid[to]!='.'){
nxt.push_back(to);
}
}
}
if((ll)nxt.size()==0)break;
for(ll j:nxt)que.push(j);
}
cout<<ans<<"\n";
return 0;
}
Compilation message
tracks.cpp: In function 'll dest(ll, ll)':
tracks.cpp:27:1: warning: control reaches end of non-void function [-Wreturn-type]
27 | }
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
2112 ms |
679284 KB |
Time limit exceeded |
2 |
Execution timed out |
2118 ms |
401732 KB |
Time limit exceeded |
3 |
Execution timed out |
2082 ms |
368024 KB |
Time limit exceeded |
4 |
Execution timed out |
2104 ms |
210888 KB |
Time limit exceeded |
5 |
Execution timed out |
2111 ms |
669544 KB |
Time limit exceeded |
6 |
Execution timed out |
2107 ms |
393296 KB |
Time limit exceeded |
7 |
Execution timed out |
2105 ms |
368220 KB |
Time limit exceeded |
8 |
Execution timed out |
2102 ms |
362688 KB |
Time limit exceeded |
9 |
Execution timed out |
2067 ms |
347720 KB |
Time limit exceeded |
10 |
Execution timed out |
2058 ms |
455648 KB |
Time limit exceeded |
11 |
Execution timed out |
2082 ms |
492 KB |
Time limit exceeded |
12 |
Execution timed out |
2115 ms |
649440 KB |
Time limit exceeded |
13 |
Execution timed out |
2116 ms |
669492 KB |
Time limit exceeded |
14 |
Execution timed out |
2116 ms |
669508 KB |
Time limit exceeded |
15 |
Execution timed out |
2058 ms |
651972 KB |
Time limit exceeded |
16 |
Execution timed out |
2127 ms |
679108 KB |
Time limit exceeded |
17 |
Execution timed out |
2108 ms |
393420 KB |
Time limit exceeded |
18 |
Execution timed out |
2087 ms |
210924 KB |
Time limit exceeded |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
2090 ms |
228176 KB |
Time limit exceeded |
2 |
Execution timed out |
2103 ms |
642252 KB |
Time limit exceeded |
3 |
Execution timed out |
2119 ms |
469444 KB |
Time limit exceeded |
4 |
Execution timed out |
2113 ms |
388940 KB |
Time limit exceeded |
5 |
Execution timed out |
2072 ms |
355528 KB |
Time limit exceeded |
6 |
Execution timed out |
2111 ms |
340168 KB |
Time limit exceeded |
7 |
Execution timed out |
2070 ms |
380124 KB |
Time limit exceeded |
8 |
Execution timed out |
2078 ms |
227988 KB |
Time limit exceeded |
9 |
Execution timed out |
2121 ms |
688312 KB |
Time limit exceeded |
10 |
Execution timed out |
2044 ms |
204872 KB |
Time limit exceeded |
11 |
Execution timed out |
2083 ms |
297344 KB |
Time limit exceeded |
12 |
Execution timed out |
2121 ms |
345288 KB |
Time limit exceeded |
13 |
Execution timed out |
2091 ms |
642116 KB |
Time limit exceeded |
14 |
Execution timed out |
2115 ms |
654344 KB |
Time limit exceeded |
15 |
Execution timed out |
2106 ms |
205324 KB |
Time limit exceeded |
16 |
Execution timed out |
2091 ms |
504540 KB |
Time limit exceeded |
17 |
Execution timed out |
2121 ms |
413984 KB |
Time limit exceeded |
18 |
Execution timed out |
2088 ms |
233888 KB |
Time limit exceeded |
19 |
Execution timed out |
2121 ms |
390948 KB |
Time limit exceeded |
20 |
Execution timed out |
2094 ms |
504388 KB |
Time limit exceeded |
21 |
Execution timed out |
2116 ms |
400100 KB |
Time limit exceeded |
22 |
Execution timed out |
2101 ms |
355464 KB |
Time limit exceeded |
23 |
Execution timed out |
2129 ms |
531156 KB |
Time limit exceeded |
24 |
Execution timed out |
2077 ms |
213432 KB |
Time limit exceeded |
25 |
Execution timed out |
2095 ms |
269460 KB |
Time limit exceeded |
26 |
Correct |
484 ms |
14188 KB |
Output is correct |
27 |
Correct |
684 ms |
20832 KB |
Output is correct |
28 |
Execution timed out |
2071 ms |
218056 KB |
Time limit exceeded |
29 |
Execution timed out |
2101 ms |
208936 KB |
Time limit exceeded |
30 |
Execution timed out |
2110 ms |
215624 KB |
Time limit exceeded |
31 |
Execution timed out |
2125 ms |
378564 KB |
Time limit exceeded |
32 |
Execution timed out |
2095 ms |
286272 KB |
Time limit exceeded |