#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int dX[]={1,-1,0,0};
int dY[]={0,0,1,-1};
int n,s;
vector<vector<int>>dis;
pair<int,int>start,fin;
vector<vector<char>>lab;
bool des2(int x,int y,int e){
vector<vector<int>>disb(n,vector<int>(n,-1));
queue<pair<int,int>>q;
q.push({x,y});
disb[x][y]=e;
while(!q.empty()){
auto p =q.front();
q.pop();
int i=p.first,j=p.second;
for(int k=0;k<4;k++){
int nX=i+dX[k],nY=j+dY[k];
if(nX>=0 && nY>=0 && nY<n && nX<n && (lab[nX][nY]=='G' or lab[nX][nY]=='D')){
int st=disb[i][j]-e+1;
//cout<<st<<"\n";
int mini=(st)/s;
mini+=e;
//cout<<mini<<"\n";
if(dis[nX][nY]>mini){
//cout<<i<<" "<<j<<"->"<<nX<<" "<<nY<<" "<<mini<<"\n";
disb[nX][nY]=disb[i][j]+1;
q.push({nX,nY});
if(nX==fin.second && nY==fin.first) break;
}
}
}
}
//cout<<disb[fin.first][fin.second];
return disb[fin.first][fin.second]!=-1;
}
void ff(int x,int y){
for(int i=0;i<4;i++){
int nX=x+dX[i],nY=y+dY[i];
if(nX>=0 && nY>=0 && nY<n && nX<n){
if(dis[x][y]+1<dis[nX][nY]){
dis[nX][nY]=dis[x][y]+1;
ff(nX,nY);
}
}
}
}
void solve(){
cin>>n>>s;
lab.assign(n,vector<char>(n));
vector<pair<int,int>>st;
dis.assign(n,vector<int>(n,1e5));
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cin>>lab[i][j];
if(lab[i][j]=='H'){
st.push_back({i,j});
}
else if(lab[i][j]=='M'){
start.first=i;
start.second=j;
}
else if(lab[i][j]=='D'){
fin.first=i;
fin.second=j;
}
}
}
for(int i=0;i<st.size();i++){
int x=st[i].first, y=st[i].second;
dis[x][y]=0;
ff(x,y);
}
int l=0,r=n*n+1;
while(l<r-1){
int m=(l+r)/2;
if(des2(start.first,start.second,m)){
l=m;
}
else r=m-1;
}
//cout<<l<<" "<<r<<"\n";
if(des2(start.first,start.second,r)) cout<<r;
else if(des2(start.first,start.second,l)) cout<<l;
else cout<<-1;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
solve();
}
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
