#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define ar array
#define vi vector<int>
#define vii vector<vector<int>>
#define pii pair<int, int>
#define pb push_back
#define all(x) x.begin(), x.end()
#define f first
#define s second
#define endl "\n"
const int MOD = 1e9+7;
const int inf = 1e9;
const ll linf = 1e18;
// -------------------------------------------------- Main Code --------------------------------------------------
const int N = 800;
int n, s;
int arr[N][N], beesDis[N][N], bearDis[N][N];
queue<pii> bees;
pii st, en;
int di[4] = {0, 0, 1, -1}, dj[4] = {1, -1, 0, 0};
bool isVal(int i, int j) {
return (i >= 0 && j >= 0 && i < n && j < n && arr[i][j]);
}
void fillBees() {
while (!bees.empty()) {
auto f = bees.front(); bees.pop();
for (int i = 0; i < 4; i++) {
int ni = f.f+di[i], nj = f.s+dj[i];
if (isVal(ni, nj) && beesDis[ni][nj] == -1) {
beesDis[ni][nj] = beesDis[f.f][f.s]+1;
bees.push({ni, nj});
}
}
}
}
bool isPoss(int i, int j, int dis, int initTime) {
return ((dis/s)+initTime < beesDis[i][j]);
}
bool isFiss(int initTime) {
if (beesDis[st.f][st.s] <= initTime) return false;
memset(bearDis, -1, sizeof bearDis);
queue<pii> bear; bear.push({st.f, st.s});
bearDis[st.f][st.s] = 0;
while (!bear.empty()) {
auto f = bear.front(); bear.pop();
for (int i = 0; i < 4; i++) {
int ni = f.f+di[i], nj = f.s+dj[i];
if (isVal(ni, nj) && bearDis[ni][nj] == -1 && isPoss(ni, nj, bearDis[f.f][f.s]+1, initTime)) {
bearDis[ni][nj] = bearDis[f.f][f.s]+1;
bear.push({ni, nj});
}
}
}
for (int i = 0; i < 4; i++) {
int ni = en.f+di[i], nj = en.s+dj[i];
if (isVal(ni, nj) && bearDis[ni][nj] != -1) return true;
}
return false;
}
int main () {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> s;
memset(beesDis, -1, sizeof beesDis);
memset(arr, 0, sizeof arr);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
char x; cin >> x;
if (x == 'M') st = {i, j};
if (x == 'D') en = {i, j};
if (x == 'H') {
bees.push({i, j});
beesDis[i][j] = 0;
}
if (x == 'G' || x == 'M') arr[i][j] = 1;
}
}
fillBees();
int i = 0, j = n;
while (i <= j) {
int mid = (i+j)/2;
if (isFiss(mid)) ans = mid, i = mid+1;
else j = mid-1;
}
cout << i-1 << endl;
}
Compilation message
mecho.cpp: In function 'int main()':
mecho.cpp:100:26: error: 'ans' was not declared in this scope; did you mean 'abs'?
100 | if (isFiss(mid)) ans = mid, i = mid+1;
| ^~~
| abs
