#include <bits/stdc++.h>
#define val(r,c) ((F[r][(c)/16]&((unsigned int)3<<((c)%16*2)))>>((c)%16*2))
using namespace std;
const int mx=4002, ms=4000*4000+1;
vector<vector<int>> G(1,vector<int>());
//vector<int> G[ms];
int rep[ms];
unsigned int F[4000][256];
int ans=0, rt=1, d, n, m, g=1;
void bfs(){
memset(rep,0,sizeof(rep));
queue<int> node,dep;
node.push(rt);
dep.push(1);
for(;!node.empty();){
int now=node.front(), dnow=dep.front();
node.pop(); dep.pop();
if(rep[now]) continue;
rep[now]=1; d=max(d,dnow);
for(int u : G[now]){
if(!rep[u]){
node.push(u);
dep.push(dnow+1);
}
}
}
}
void input(){
scanf("%d %d\n",&n,&m);
int f;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
f=getchar();
f=(f=='F'?0:(f=='R'?1:2));
F[i][j/16]|=((unsigned int)f<<(j%16*2));
}
getchar();
}
}
void gennode(){
for(int now=0;now<n*m;++now){
if(rep[now]|| val(now/m,now%m)==2) continue;
//printf("%d %d\n",now/m+1,now%m+1);
G.push_back(vector<int>());
stack<int> Q;
Q.push(now); rep[now]=g;
int cvar=val(now/m,now%m),var,r;
for(int p;!Q.empty();){
p=Q.top(); Q.pop();
//printf("%d\n",val(p/m,p%m));
rep[p]=g;
if(p%m<m-1){
r=p+1;
var=val(r/m,r%m);
if(var==cvar && !rep[r]){
rep[r]=g;
Q.push(r);
}
else if(var!=2){
if(rep[r] && var!=cvar && (G[rep[r]].empty() || G[rep[r]].back()!=g)){
G[g].push_back(rep[r]);
G[rep[r]].push_back(g);
}
}
}
if(p%m>0){
r=p-1;
var=val(r/m,r%m);
if(var==cvar && !rep[r]){
rep[r]=g;
Q.push(r);
}
else if(var!=2){
if(rep[r] && var!=cvar && (G[rep[r]].empty() || G[rep[r]].back()!=g)){
G[g].push_back(rep[r]);
G[rep[r]].push_back(g);
}
}
}
if(p/m<n-1){
r=p+m;
var=val(r/m,r%m);
if(var==cvar && !rep[r]){
rep[r]=g;
Q.push(r);
}
else if(var!=2){
if(rep[r] && var!=cvar && (G[rep[r]].empty() || G[rep[r]].back()!=g)){
G[g].push_back(rep[r]);
G[rep[r]].push_back(g);
}
}
}
if(p/m>0){
r=p-m;
var=val(r/m,r%m);
if(var==cvar && !rep[r]){
rep[r]=g;
Q.push(r);
}
else if(var!=2){
if(rep[r] && var!=cvar && (G[rep[r]].empty() || G[rep[r]].back()!=g)){
G[g].push_back(rep[r]);
G[rep[r]].push_back(g);
}
}
}
}
++g;
}
}
int main(){
input();
gennode();
/*
printf("%d\n",g);
for(int i=1;i<g;i++,puts("")) for(int x : G[i]) printf("%d ",x);
*/
bfs();
printf("%d\n",d);
return 0;
}
Compilation message
tracks.cpp: In function 'void input()':
tracks.cpp:29:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d\n",&n,&m);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
63 ms |
72060 KB |
Output is correct |
| 2 |
Correct |
6 ms |
68528 KB |
Output is correct |
| 3 |
Correct |
6 ms |
68528 KB |
Output is correct |
| 4 |
Correct |
13 ms |
68828 KB |
Output is correct |
| 5 |
Correct |
9 ms |
69012 KB |
Output is correct |
| 6 |
Correct |
9 ms |
68528 KB |
Output is correct |
| 7 |
Correct |
3 ms |
68528 KB |
Output is correct |
| 8 |
Correct |
3 ms |
68528 KB |
Output is correct |
| 9 |
Correct |
9 ms |
68528 KB |
Output is correct |
| 10 |
Correct |
13 ms |
69012 KB |
Output is correct |
| 11 |
Correct |
3 ms |
68660 KB |
Output is correct |
| 12 |
Correct |
26 ms |
69408 KB |
Output is correct |
| 13 |
Correct |
9 ms |
69012 KB |
Output is correct |
| 14 |
Correct |
19 ms |
69012 KB |
Output is correct |
| 15 |
Correct |
36 ms |
71924 KB |
Output is correct |
| 16 |
Correct |
49 ms |
72060 KB |
Output is correct |
| 17 |
Correct |
36 ms |
71920 KB |
Output is correct |
| 18 |
Correct |
16 ms |
68828 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
69008 KB |
Output is correct |
| 2 |
Correct |
183 ms |
82000 KB |
Output is correct |
| 3 |
Correct |
1293 ms |
175420 KB |
Output is correct |
| 4 |
Correct |
299 ms |
82616 KB |
Output is correct |
| 5 |
Execution timed out |
2000 ms |
494544 KB |
Execution timed out |
| 6 |
Correct |
1519 ms |
124624 KB |
Output is correct |
| 7 |
Correct |
9 ms |
69008 KB |
Output is correct |
| 8 |
Correct |
16 ms |
69008 KB |
Output is correct |
| 9 |
Correct |
23 ms |
69012 KB |
Output is correct |
| 10 |
Correct |
6 ms |
68812 KB |
Output is correct |
| 11 |
Correct |
6 ms |
68812 KB |
Output is correct |
| 12 |
Correct |
6 ms |
69396 KB |
Output is correct |
| 13 |
Correct |
199 ms |
82000 KB |
Output is correct |
| 14 |
Correct |
116 ms |
75324 KB |
Output is correct |
| 15 |
Correct |
136 ms |
81864 KB |
Output is correct |
| 16 |
Correct |
89 ms |
75280 KB |
Output is correct |
| 17 |
Correct |
519 ms |
97344 KB |
Output is correct |
| 18 |
Correct |
569 ms |
121788 KB |
Output is correct |
| 19 |
Correct |
296 ms |
82616 KB |
Output is correct |
| 20 |
Correct |
313 ms |
95304 KB |
Output is correct |
| 21 |
Correct |
719 ms |
122052 KB |
Output is correct |
| 22 |
Execution timed out |
2000 ms |
494544 KB |
Execution timed out |
| 23 |
Correct |
956 ms |
124808 KB |
Output is correct |
| 24 |
Correct |
1002 ms |
175020 KB |
Output is correct |
| 25 |
Execution timed out |
2000 ms |
281484 KB |
Execution timed out |
| 26 |
Correct |
1136 ms |
93824 KB |
Output is correct |
| 27 |
Correct |
1199 ms |
77188 KB |
Output is correct |
| 28 |
Correct |
1646 ms |
124624 KB |
Output is correct |
| 29 |
Correct |
1466 ms |
96540 KB |
Output is correct |
| 30 |
Correct |
1386 ms |
84136 KB |
Output is correct |
| 31 |
Execution timed out |
2000 ms |
181888 KB |
Execution timed out |
| 32 |
Correct |
1213 ms |
82044 KB |
Output is correct |
