Submission #564940

#TimeUsernameProblemLanguageResultExecution timeMemory
564940Garguy22Tracks in the Snow (BOI13_tracks)C++17
100 / 100
745 ms131072 KiB
#include <iostream> #include <queue> using namespace std; typedef pair<int, int> pii; #define mp make_pair #define ff first #define ss second int n, m; char grid[4007][4007]; int depth[4007][4007]; int dx[4] = {1, -1, 0, 0}; int dy[4] = {0, 0, 1, -1}; bool chk(int x, int y) { return (x > -1 && x < n && y > -1 && y < m && grid[x][y] != '.'); } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> m; for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++) cin >> grid[i][j]; } int ans = 1; deque<pii> q; q.push_back(mp(0, 0)); depth[0][0] = 1; while(q.size()){ pii u = q.front(); q.pop_front(); ans = max(ans, depth[u.ff][u.ss]); for(int i = 0; i < 4; i++){ int x = u.ff + dx[i], y = u.ss + dy[i]; if(chk(x, y) && depth[x][y] == 0){ if(grid[x][y] == grid[u.ff][u.ss]){ depth[x][y] = depth[u.ff][u.ss]; q.push_front(mp(x, y)); }else{ depth[x][y] = depth[u.ff][u.ss] + 1; q.push_back(mp(x, y)); } } } } cout << ans << endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...