Submission #595044

#TimeUsernameProblemLanguageResultExecution timeMemory
595044ShivanshJTracks in the Snow (BOI13_tracks)C++17
100 / 100
1766 ms922000 KiB
#include <bits/stdc++.h> #define int long long using namespace std; const int MAX=4e3+5; const int INF=1e18; const int MOD=1e9+7; const int MAXL=32; int dx[]={-1,0,1,0},dy[]={0,1,0,-1}; int g[MAX][MAX][6],h,w; // {T,R,B,L} , vertex-info (4) bool chk(int x,int y) { return (x>=0 && y>=0 && x<h && y<w && g[x][y][4]!=-1); } signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); //cout<<setprecision(6)<<fixed; //freopen("input.txt","r",stdin); //freopen("output.txt","w",stdout); cin>>h>>w; for(int i=0;i<h;i++) { for(int j=0;j<w;j++) { char s; cin>>s; if(s=='R') { g[i][j][4]=0; } else if(s=='F') { g[i][j][4]=1; } else { g[i][j][4]=-1; } } } for(int i=0;i<h;i++) { for(int j=0;j<w;j++) { for(int z=0;z<4;z++) { int nx=i+dx[z],ny=j+dy[z]; if(chk(nx,ny) && g[nx][ny][4]!=g[i][j][4]) { g[i][j][z]=1; } } g[i][j][5]=-1; } } deque<tuple<int,int,int>>dq; //{x,y,dist} dq.push_front({0,0,0}); int ans=0; while(!dq.empty()) { tuple<int,int,int>curr=dq.front(); dq.pop_front(); int x=get<0>(curr),y=get<1>(curr),d=get<2>(curr); if(g[x][y][5]!=-1) { continue; } g[x][y][5]=d; ans=max(ans,d); for(int i=0;i<4;i++) { int nx=x+dx[i],ny=y+dy[i]; if(!chk(nx,ny) || g[nx][ny][5]!=-1) { continue; } if(g[x][y][i]) { dq.push_back({nx,ny,d+1}); } else { dq.push_front({nx,ny,d}); } } } cout<<(++ans); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...