#include <bits/stdc++.h>
/*--------------------------------------------------------------------*/
#define INF 3*100*1000 + 5
#define MAX 1000000
#define pb push_back
#define fi first
#define se second
#define pii pair<int, int>
#define vi vector<int>
#define vvi vector<vector<int>>
#define intt int64_t
#define piic pair<int64_t, int64_t>
typedef long long ll;
using namespace std;
/*--------------------------------------------------------------------*/
int n, s;
pii b, home;
queue<pii> hives;
vector<string> grid;
int filltime[900][900]{INT_MAX}, beetime[900][900], visited[900][900];
int dx[4]{1, -1, 0, 0}, dy[4]{0, 0, 1, -1};
int inside(int x, int y){
return (x> -1 && x < n && y > -1 && y < n && grid[x][y] != 'T');
}
int main(int argc, const char * argv[]) {
ios::sync_with_stdio(0); cin.tie(0);
fill(filltime[0], filltime[0] + 900*900, INT_MAX);
if(2 >= INT_MAX) cout << "Error\n";
cin >> n >> s;
for(int i = 0; i < n; ++i){
string str;
cin >> str;
grid.pb(str);
for(int j = 0; j < (int)str.length(); ++j){
if (str[j] == 'M') b = make_pair(i, j);
if (str[j] == 'D') home = make_pair(i, j);
if(str[j] == 'H'){
hives.push(make_pair(i, j));
filltime[i][j] = 0;
}
}
}
while(!hives.empty()){
pii bee = hives.front();
hives.pop();
int x,y;
x = bee.fi; y = bee.se;
for(int i = 0; i < 4; ++i){
if(!inside(x + dx[i], y + dy[i]) || grid[x+dx[i]][y+dy[i]] == 'D') continue;
if(filltime[x+dx[i]][y+dy[i]] != INT_MAX)
filltime[x+dx[i]][y+dy[i]] = min(filltime[x+dx[i]][y+dy[i]], filltime[x][y] + 1);
else {
filltime[x+dx[i]][y+dy[i]] = filltime[x][y] + 1;
hives.push(make_pair(x + dx[i], y + dy[i]));
}
}
}
int lo = 0, hi = filltime[b.fi][b.se];
int ans = 0;
bool realpos = false;
while(lo < hi){
queue<tuple<int, int, int, int>> q;
int tempans = lo + (hi-lo)/2;
bool pos = false;
fill(visited[0], visited[0] + 900*900, 0);
visited[b.fi][b.se] = 1;
q.push(make_tuple(b.fi, b.se, tempans, 0));
// cout << "New Round " << tempans << '\n';
while(!q.empty()){
tuple<int, int, int, int> cur = q.front();
q.pop();
int x = get<0>(cur);
int y = get<1> (cur);
int a = get<2> (cur);
int res = get<3> (cur);
//cout << x << ' ' << y << ' ' << a << ' ' << res << ' ' << q.size() << ' ' << filltime[x][y] << '\n';
if(a + (double)res/s >= filltime[x][y]) continue;
if(x == home.fi && y == home.se) {
pos = true;
realpos = true;
// cout << "Success!\n";
break;
}
int x1, y1;
if(res == s-1) {
y1 = 0;
x1 = a + 1;
} else {
x1 = a;
y1 = res + 1;
}
for(int i = 0; i < 4; ++i) {
if(!inside(x+dx[i],y+dy[i])) continue;
if(visited[x+dx[i]][y+dy[i]]) continue;
visited[x+dx[i]][y+dy[i]] = 1;
q.push(make_tuple(x+dx[i], y+dy[i], x1, y1));
}
}
// cout << pos << '\n';
if(realpos) {
ans = max(ans, tempans);
lo = tempans + 1;
} else {
hi = tempans;
}
}
if(pos) cout << ans << '\n';
else cout << -1 << '\n';
return 0;
}
Compilation message
mecho.cpp: In function 'int main(int, const char**)':
mecho.cpp:73:14: warning: variable 'pos' set but not used [-Wunused-but-set-variable]
73 | bool pos = false;
| ^~~
mecho.cpp:119:8: error: 'pos' was not declared in this scope; did you mean 'pow'?
119 | if(pos) cout << ans << '\n';
| ^~~
| pow
