Submission #1249140

#TimeUsernameProblemLanguageResultExecution timeMemory
1249140papauloTracks in the Snow (BOI13_tracks)C++20
80.31 / 100
2125 ms1114112 KiB
#include <bits/stdc++.h> using namespace std; #define MAXD 4040 char mat[MAXD][MAXD]; short breadth[MAXD][MAXD]; vector<pair<short, short>> perb[MAXD*MAXD]; const int dy[4]={0, 1, 0, -1}; const int dx[4]={1, 0, -1, 0}; int main() { memset(mat, '.', sizeof(mat)); memset(breadth, 0, sizeof(breadth)); cin.tie(nullptr); ios::sync_with_stdio(false); int h, w; cin >> h >> w; for(int i=1;i<=h;i++) for(int j=1;j<=w;j++) cin >> mat[i][j]; breadth[1][1]=1; perb[1].push_back({1, 1}); for(int cur=1;!perb[cur].empty();cur++) { for(int i=0;i<perb[cur].size();i++) { auto pr=perb[cur][i]; int y=pr.first, x=pr.second; for(int k=0;k<4;k++) { int newy=y+dy[k]; int newx=x+dx[k]; if(!breadth[newy][newx]&&mat[newy][newx]==mat[y][x]) { breadth[newy][newx]=breadth[y][x]; perb[cur].push_back({newy, newx}); } } } for(auto pr : perb[cur]) { int y=pr.first, x=pr.second; for(int k=0;k<4;k++) { int newy=y+dy[k]; int newx=x+dx[k]; if(!breadth[newy][newx]&&mat[newy][newx]!='.') { breadth[newy][newx]=breadth[y][x]+1; perb[cur+1].push_back({newy, newx}); } } } } int ans=0; for(int i=1;i<=h;i++) for(int j=1;j<=w;j++) ans=max(ans, (int) breadth[i][j]); cout << ans << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...