Submission #1191976

#TimeUsernameProblemLanguageResultExecution timeMemory
1191976ChuanChenTracks in the Snow (BOI13_tracks)C++20
11.56 / 100
467 ms97900 KiB
#include<bits/stdc++.h> using namespace std; #define ss second #define ff first typedef pair<int, int> pii; const int lim = 4e3+5; char c[lim][lim]; int d[lim][lim]; bool marc[lim][lim]; int H, W, ans; bool inbound(int x, int y){ return 1<=x&&x<=H && 1<=y&&y<=W; } int main(){ cin.tie(0)->sync_with_stdio(0); cin >> H >> W; for(int i = 1; i <= H; i++){ for(int j = 1; j <= W; j++){ cin >> c[i][j]; } } deque<pii> dq; dq.push_back({1, 1}); d[1][1] = 1; int dx[] = {1, 0, -1, 0}; int dy[] = {0, 1, 0, -1}; while(!dq.empty()){ auto [x, y] = dq.front(); dq.pop_front(); marc[x][y] = true; ans = max(ans, d[x][y]); for(int i = 0; i < 3; i++){ int nx = x+dx[i], ny = y+dy[i]; if(c[nx][ny] == '.' || !inbound(nx, ny) || marc[nx][ny]) continue; if(d[nx][ny] == 0){ if(c[nx][ny] == c[x][y]){ d[nx][ny] = d[x][y]; dq.push_front({nx, ny}); } else{ d[nx][ny] = d[x][y]+1; dq.push_back({nx, ny}); } } } } cout << ans << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...