제출 #581540

#제출 시각아이디문제언어결과실행 시간메모리
581540alexddTracks in the Snow (BOI13_tracks)C++17
100 / 100
1554 ms122036 KiB
#include<iostream> #include<deque> using namespace std; int n,m; char mat[4001][4001]; int dirlin[4]={1,-1,0,0}; int dircol[4]={0,0,1,-1}; deque<int> dqlin; deque<int> dqcol; int best[4001][4001]; bool good(int lin, int col) { if(lin>=1 && lin<=n && col>=1 && col<=m) return 1; return 0; } int main() { cin>>n>>m; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) {cin>>mat[i][j];best[i][j]=4000*4000+100;} dqlin.push_back(1); dqcol.push_back(1); best[1][1]=1; int lin,col; while(dqlin.empty()==0) { lin=dqlin.front(); col=dqcol.front(); dqlin.pop_front(); dqcol.pop_front(); for(int i=0;i<4;i++) { if(good(lin+dirlin[i], col+dircol[i]) && mat[lin+dirlin[i]][col+dircol[i]]!='.' && best[lin][col]+(mat[lin][col]!=mat[lin+dirlin[i]][col+dircol[i]])<best[lin+dirlin[i]][col+dircol[i]]) { best[lin+dirlin[i]][col+dircol[i]]=best[lin][col]+(mat[lin][col]!=mat[lin+dirlin[i]][col+dircol[i]]); if(mat[lin][col]!=mat[lin+dirlin[i]][col+dircol[i]]) { dqlin.push_back(lin+dirlin[i]); dqcol.push_back(col+dircol[i]); } else { dqlin.push_front(lin+dirlin[i]); dqcol.push_front(col+dircol[i]); } } } } int mxm=0; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) if(mat[i][j]!='.') mxm=max(mxm,best[i][j]); } cout<<mxm; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...