제출 #1187274

#제출 시각아이디문제언어결과실행 시간메모리
1187274pxsitTracks in the Snow (BOI13_tracks)C++20
100 / 100
416 ms89616 KiB
#include <bits/stdc++.h> using namespace std; int main(){ ios::sync_with_stdio(false); cin.tie(NULL); int h,w; cin>>h>>w; vector<string> g(h); for(int i=0;i<h;i++) cin>>g[i]; int n=h*w; const int INF=1e9; vector<int> dist(n,INF); deque<int> dq; dist[0]=0; dq.push_front(0); int dr[4]={-1,1,0,0}, dc[4]={0,0,-1,1}; while(!dq.empty()){ int id=dq.front(); dq.pop_front(); int d=dist[id]; int r=id/w, c=id%w; for(int k=0;k<4;k++){ int nr=r+dr[k], nc=c+dc[k]; if(nr<0||nr>=h||nc<0||nc>=w) continue; if(g[nr][nc]=='.') continue; int nid=nr*w+nc; int w1 = g[nr][nc]!=g[r][c]; if(dist[nid]>d+w1){ dist[nid]=d+w1; if(w1==0) dq.push_front(nid); else dq.push_back(nid); } } } int mx=0; for(int i=0;i<h;i++) for(int j=0;j<w;j++) if(g[i][j]!='.') mx=max(mx,dist[i*w+j]); cout<<mx+1; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...