#include<bits/stdc++.h>
using namespace std;
#define fff first
#define sss second
int di[]={1,-1,0,0};
int dj[]={0,0,1,-1};
struct st
{
int i,j,w;
};
struct e
{
int i,j,sec,step;
};
int main()
{
int n,ss;
cin>>n>>ss;
string s[n];
int mx,my,dx,dy;
int t[n][n];
memset(t,-1,sizeof t);
queue<st> q;
for(int i=0;i<n;i++)
{
cin>>s[i];
for(int j=0;j<n;j++)
{
if(s[i][j]=='M')
mx=i,my=j;
if(s[i][j]=='D')
dx=i,dy=j;
if(s[i][j]=='H')
{
t[i][j]=0;
q.push({i,j,0});
}
}
}
while(!q.empty())
{
auto p=q.front();
q.pop();
int i=p.i,j=p.j,w=p.w;
if(t[i][j]<w)
continue;
for(int k=0;k<4;k++)
{
int ii=i+di[k],jj=j+dj[k];
if(ii<0||ii>=n||jj<0||jj>=n)
continue;
if(t[ii][jj]==-1&&s[ii][jj]=='G'||s[ii][jj]=='M')
{
t[ii][jj]=w+1;
q.push({ii,jj,w+1});
}
}
}
/*for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
cout<<t[i][j]<<' ';
cout<<endl;
}*/
int dist[n][n];
int l=-1,r=n*n;
while(l<r)
{
int mid=(l+r+1)/2;
memset(dist,-1,sizeof dist);
queue<e> qq;
qq.push({mx,my,mid,ss});
dist[mx][my]=mid;
if(t[mx][my]!=-1&&t[mx][my]<mid)
{
r=mid-1;
continue;
}
while(!qq.empty())
{
auto p=qq.front();
qq.pop();
int i=p.i,j=p.j,sec=p.sec,step=p.step;
if(step==ss)
{
step=1;
sec++;
}
else
step++;
//cout<<sec<<" ";
for(int k=0;k<4;k++)
{
int ii=i+di[k],jj=j+dj[k];
if(ii<0||ii>=n||jj<0||jj>=n)
continue;
if(dist[ii][jj]==-1)
{
if((s[ii][jj]=='G'&&(t[ii][jj]>=sec||t[ii][jj]==-1))||s[ii][jj]=='D')
{
dist[ii][jj]=sec;
qq.push({ii,jj,sec,step});
}
}
}
}
//cout<<mid<<' ';
if(dist[dx][dy]!=-1)
l=mid;
else
r=mid-1;
/*for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
cout<<dist[i][j]<<' ';
cout<<endl;
}*/
}
cout<<l;
}
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
