제출 #731552

#제출 시각아이디문제언어결과실행 시간메모리
731552kirakaminski968Tracks in the Snow (BOI13_tracks)C++17
100 / 100
665 ms139368 KiB
#include <bits/stdc++.h> using namespace std; int dx[4] = {0,1,-1,0}; int dy[4] = {1,0,0,-1}; int dist[4000][4000]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int H,W; cin >> H >> W; vector<string> grid(H); for(int i = 0;i<H;++i) cin >> grid[i]; deque<pair<int,int>> q; q.push_front({0,0}); dist[0][0] = 1; int ans = 1; while(!q.empty()){ int x = q.front().first, y = q.front().second; q.pop_front(); ans = max(ans,dist[x][y]); for(int i = 0;i<4;++i){ int nx = x+dx[i], ny = y+dy[i]; if(nx < 0 || nx >= H || ny < 0 || ny >= W) continue; if(grid[nx][ny] == '.' || dist[nx][ny] != 0) continue; if(grid[nx][ny] == grid[x][y]){ dist[nx][ny] = dist[x][y]; q.push_front({nx,ny}); } else{ dist[nx][ny] = dist[x][y]+1; q.push_back({nx,ny}); } } } cout << ans << "\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...