# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1088857 | StefanSebez | Mecho (IOI09_mecho) | C++14 | 156 ms | 8028 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
vector<string>a;
bool was[850][850];
int depth[850][850],dist[850][850],n,S;
bool Dobar(int x,int y){
if(x<0||x>=n||y<0||y>=n||a[x][y]=='T'||was[x][y]) return false;
return true;
}
int main(){
scanf("%i%i",&n,&S);
for(int i=0;i<n;i++){string s;cin>>s;a.pb(s);}
int X0,Y0,X1,Y1;
vector<pair<int,int> >H;
for(int i=0;i<n;i++) for(int j=0;j<n;j++){if(a[i][j]=='M'){X0=i,Y0=j;}if(a[i][j]=='H')H.pb({i,j});if(a[i][j]=='D'){X1=i,Y1=j;}}
queue<pair<int,int> >kju;
for(auto i:H){kju.push(i);was[i.fi][i.se]=true;}
while(kju.size()){
int u=kju.front().fi,v=kju.front().se;kju.pop();
if(Dobar(u-1,v)){depth[u-1][v]=depth[u][v]+1;was[u-1][v]=true;kju.push({u-1,v});}
if(Dobar(u+1,v)){depth[u+1][v]=depth[u][v]+1;was[u+1][v]=true;kju.push({u+1,v});}
if(Dobar(u,v-1)){depth[u][v-1]=depth[u][v]+1;was[u][v-1]=true;kju.push({u,v-1});}
if(Dobar(u,v+1)){depth[u][v+1]=depth[u][v]+1;was[u][v+1]=true;kju.push({u,v+1});}
}
//for(int i=0;i<n;i++) {for(int j=0;j<n;j++) printf("%i ",depth[i][j]);printf("\n");}
int l=0,r=2000,res=-1;
while(l<=r){
//printf("%i %i**\n",l,r);
int mid=l+r>>1;
for(int i=0;i<=n;i++) for(int j=0;j<=n;j++) {dist[i][j]=0;was[i][j]=false;}
kju.push({X0,Y0});was[X0][Y0]=true;
bool moze=false;
for(int i=S,dst=mid;dst<=2000;i+=S,dst++){
while(kju.size()){
int u=kju.front().fi,v=kju.front().se;
//printf("%i %i\n",u,v);
if(u==X1 && v==Y1) moze=true;
if(dist[u][v]==i) break;
kju.pop();
if(Dobar(u-1,v)&&depth[u-1][v]>dst){dist[u-1][v]=dist[u][v]+1;was[u-1][v]=true;kju.push({u-1,v});}
if(Dobar(u+1,v)&&depth[u+1][v]>dst){dist[u+1][v]=dist[u][v]+1;was[u+1][v]=true;kju.push({u+1,v});}
if(Dobar(u,v-1)&&depth[u][v-1]>dst){dist[u][v-1]=dist[u][v]+1;was[u][v-1]=true;kju.push({u,v-1});}
if(Dobar(u,v+1)&&depth[u][v+1]>dst){dist[u][v+1]=dist[u][v]+1;was[u][v+1]=true;kju.push({u,v+1});}
}
}
if(moze) res=mid,l=mid+1;
else r=mid-1;
}
printf("%i\n",res);
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |