Submission #1191978

#TimeUsernameProblemLanguageResultExecution timeMemory
1191978ChuanChenTracks in the Snow (BOI13_tracks)C++20
11.56 / 100
485 ms98052 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; int dx[] = {1, 0, -1, 0}; int dy[] = {0, 1, 0, -1}; 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; marc[1][1] = true; while(!dq.empty()){ auto [x, y] = dq.front(); dq.pop_front(); 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(c[nx][ny] == c[x][y]){ d[nx][ny] = d[x][y]; dq.push_front({nx, ny}); marc[nx][ny] = true; } else{ d[nx][ny] = d[x][y]+1; dq.push_back({nx, ny}); marc[nx][ny] = true; } } } cout << ans << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...