Submission #649076

#TimeUsernameProblemLanguageResultExecution timeMemory
649076anirudh001Tracks in the Snow (BOI13_tracks)C++17
100 / 100
868 ms111872 KiB
#include<bits/stdc++.h> #define ll long long using namespace std; const int nm = 1e6; bool isValid(int x, int y, int n, int m, string snow[]){ if(x>=0 && x<n && y>=0 && y<m && snow[x][y]!='.')return true; return false; } int main(){ ll h, w; cin >> h >> w; string snow[h]; for(int i = 0; i<h; i++)cin >> snow[i]; vector<vector<int>> depth(h, vector<int>(w)); deque<pair<int, int>> q; q.push_back({0, 0}); depth[0][0] =1; int dx[4] = {0, 0, 1, -1}; int dy[4] = {1, -1, 0, 0}; int ans = 0; while(!q.empty()){ int i = q.front().first; int j = q.front().second; ans = max(depth[i][j], ans); q.pop_front(); for(int k = 0; k<4; k++){ int x = i + dx[k], y = j + dy[k]; if(isValid(x, y, h, w, snow) && depth[x][y]==0){ if(snow[x][y]==snow[i][j]){ q.push_front({x, y}); depth[x][y] = depth[i][j]; } else{ q.push_back({x, y}); depth[x][y] = depth[i][j] +1; } } } } cout << ans << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...