#include <bits/stdc++.h>
using namespace std;
//Soltan Cristian
#define ll long long
#define all(x) x.begin(), x.end()
#define mod 1000000007
#define pb push_back
#define st first
#define nd second
#define sz(x) (ll)x.size()
#define rall(x) x.rbegin(), x.rend()
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
const int mxa = 2 * 1e5 + 2;
// string __fname = "maxflow";
// ifstream in(__fname + ".in");
// ofstream out (__fname + ".out");
// #define cin in
// #define cout out
int n, s;
vector<vector<char>> mapa;
bool validB(int x, int y){
if(x >= 0 && x < n && y >= 0 && y < n && mapa[x][y] != 'T' && mapa[x][y] != 'D'){
return true;
}
return false;
}
bool valid(int x, int y){
if(x >= 0 && x < n && y >= 0 && y < n && mapa[x][y] != 'T'){
return true;
}
return false;
}
void solve(){
cin >> n >> s;
mapa = vector<vector<char>>(n, vector<char>(n));
vector<pair<int,int>> stup;
pair<int, int> start, finish;
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
char x;
cin >> x;
if(x == 'H') stup.pb({i, j});
if(x == 'M') start = {i, j};
if(x == 'D') finish = {i, j};
mapa[i][j] = x;
}
}
vector<vector<int>> bees(n, vector<int>(n, INT_MAX));
queue<pair<int, int>> qB;
for(int i = 0; i < sz(stup); i++){
bees[stup[i].st][stup[i].nd] = 0;
qB.push({stup[i].st, stup[i].nd});
}
// cout << "a\n";
while(!qB.empty()){
pair<int, int> u = qB.front();
qB.pop();
for(int i = 0; i < 4; i++){
if(!validB(u.st + dx[i], u.nd + dy[i])) continue;
if(bees[u.st][u.nd] + s < bees[u.st + dx[i]][u.nd + dy[i]]){
qB.push({u.st + dx[i], u.nd + dy[i]});
bees[u.st + dx[i]][u.nd + dy[i]] = bees[u.st][u.nd] + s;
}
}
}
if(bees[start.st][start.nd] == INT_MAX){
cout << -1 << '\n';
return;
}
int l = 0, r = 2 * n * n;
int ans = -1;
while(l <= r){
int mid = (l + r) / 2;
vector<vector<int>> h(n, vector<int>(n, INT_MAX));
h[start.st][start.nd] = mid;
queue<pair<int,int>> q;
q.push({start.st, start.nd});
while(!q.empty()){
pair<int, int> u = q.front();
q.pop();
for(int i = 0; i < 4; i++){
if(!valid(u.st + dx[i], u.nd + dy[i])) continue;
if(h[u.st][u.nd] + 1 < bees[u.st + dx[i]][u.nd + dy[i]] &&
h[u.st][u.nd] + 1 < h[u.st + dx[i]][u.nd + dy[i]]){
q.push({u.st + dx[i], u.nd + dy[i]});
h[u.st + dx[i]][u.nd + dy[i]] = h[u.st][u.nd] + 1;
}
}
}
if(h[finish.st][finish.nd] < INT_MAX){
cout << mid << ' ' << ans << '\n';
ans = max(ans, mid);
l = mid + 1;
}
else r = mid - 1;
}
// cout << ans << '\n';
// if(ans == -1){
// cout << -1<< '\n';
// }
else cout << ans / s << '\n';
}
int main()
{
// ios_base::sync_with_stdio(0); cin.tie(0); cout << fixed << (setprecision(10));
// int t;
// cin >> t;
// while(t--)
solve();
return 0;
}
Compilation message
mecho.cpp: In function 'void solve()':
mecho.cpp:108:5: error: 'else' without a previous 'if'
108 | else cout << ans / s << '\n';
| ^~~~
