#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N = 801,INF=1e12;
int n , o, srcx, srcy, destx, desty, ar[N][N],arr[N][N],arr2[N][N];
int dx[4]={0,-1,1,0};
int dy[4]={-1,0,0,1};
bool vis[N][N];
bool valid(int x, int y){
if(x>=0 && x<n && y>=0 && y<n) return true;
return false;
}
bool check(int mins)
{
memset(vis,0,sizeof vis);
memset(arr2,0,sizeof arr2);
queue<pair<int,int>>qq;
qq.push({srcx,srcy});
vis[srcx][srcy]=1;
if(arr[srcx][srcy]<=mins) return false;
arr2[srcx][srcy]=0;
while(!qq.empty()){
int curx=qq.front().first;
int cury=qq.front().second;
qq.pop();
for(int i = 0 ; i < 4; i ++)
{
int gox = curx+dx[i], goy = cury+dy[i];
if(valid(gox,goy) && !vis[gox][goy] && ar[gox][goy]!=-1){
if(arr[gox][goy] > floor((double)(arr2[curx][cury]+1)/(double)o)+mins){
// cout<<curx<<" "<<cury<<" "<<gox<<" "<<goy<<" "<<arr2[curx][cury]<<" "<<arr[gox][goy]-mins<<" "<<c<<" "<<arr2[curx][cury]+(c%o==0&&c>0)<<endl;
vis[gox][goy]=1;
arr2[gox][goy]=arr2[curx][cury]+1;
if(gox==destx&&goy==desty) return true;
qq.push({gox,goy});
}
}
}
}
return false;
}
void bfs(){
queue<pair<int,int>>q;
memset(vis,0,sizeof vis);
for(int i = 0 ; i < n ; i ++)
for(int j = 0 ; j < n ; j ++)
{
if(ar[i][j]==1){
q.push({i,j});
vis[i][j]=1;
arr[i][j]=0;
}
}
while(!q.empty())
{
int curx=q.front().first;
int cury=q.front().second;
q.pop();
for(int i = 0 ; i < 4; i ++)
{
int gox = curx+dx[i], goy = cury+dy[i];
if(valid(gox,goy) && !vis[gox][goy] && ar[gox][goy]!=-1 && (destx!=gos || desty!=goy)){
vis[gox][goy]=1;
arr[gox][goy]=arr[curx][cury]+1;
q.push({gox,goy});
}
}
}
}
int32_t main()
{
//freopen("abc.in", "r", stdin);
cin >> n >> o;
for(int i = 0 ; i < n ; i ++){
for(int j = 0 ; j < n ; j ++){
char x; cin >> x;
arr[i][j]=1e9;
ar[i][j] = (x=='H'?1:((x=='G'||x=='D'||x=='M')?0:-1));
if(x=='M') srcx=i, srcy=j;
if(x=='D') destx=i, desty=j;
}
}
bfs();
int l = 0 , r = 1e9;
int ans=-1;
while(l <= r)
{
int mid = l + (r - l) / 2;;
// cout<<mid<<endl;
if(check(mid))
{
l = mid+1;
ans=mid;
}
else
{
r = mid-1;
}
}
cout<<ans<<endl;
}
Compilation message
mecho.cpp: In function 'void bfs()':
mecho.cpp:70:74: error: 'gos' was not declared in this scope; did you mean 'goy'?
70 | if(valid(gox,goy) && !vis[gox][goy] && ar[gox][goy]!=-1 && (destx!=gos || desty!=goy)){
| ^~~
| goy
