Submission #1249143

#TimeUsernameProblemLanguageResultExecution timeMemory
1249143papauloTracks in the Snow (BOI13_tracks)C++20
2.19 / 100
166 ms79088 KiB
#include <bits/stdc++.h> using namespace std; const int dy[4]={0, 1, 0, -1}; const int dx[4]={1, 0, -1, 0}; int main() { cin.tie(nullptr); ios::sync_with_stdio(false); int h, w; cin >> h >> w; vector<vector<char>> mat(h+2, vector<char>(w+2, '.')); vector<vector<int>> breadth(h+2, vector<int>(w+2, 0)); for(int i=1;i<=h;i++) for(int j=1;j<=w;j++) cin >> mat[i][j]; breadth[1][1]=1; vector<pair<int, int>> perb[2]; perb[0].push_back({1, 1}); for(int cur=0;!perb[cur].size(); cur^=1) { 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}); } } } perb[cur].clear(); } int ans=0; for(int i=1;i<=h;i++) for(int j=1;j<=w;j++) ans=max(ans, breadth[i][j]); cout << ans << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...