#include <iostream>
#include <queue>
#include <stack>
#include <vector>
// Global variables
int N{ 0 };
int S{ 0 };
bool isInBounds(int i, int j) {
return (i >= 0 && i < N && j >= 0 && j < N);
}
bool isBearWalkable(int i, int j, const std::vector<std::string>& forest) {
return (forest[i][j] == 'G' || forest[i][j] == 'D');
}
bool isBeeWalkable(int i, int j, const std::vector<std::string>& forest) {
return (forest[i][j] == 'G' || forest[i][j] == 'M');
}
bool isNotVisited(int i, int j, const std::vector<std::vector<bool>>& visited) {
return (!visited[i][j]);
}
bool isBearCandidate(int i, int j, const std::vector<std::string>& forest, const std::vector<std::vector<bool>>& visited) {
return ( isInBounds(i, j)
&& isBearWalkable(i, j, forest)
&& isNotVisited(i, j, visited) );
}
bool isBeeCandidate(int i, int j, const std::vector<std::string>& forest) {
return ( isInBounds(i, j)
&& isBeeWalkable(i, j, forest));
}
void addBeeCandidate(int t, int i, int j, int current_i, int current_j, std::vector<std::string>& forest, std::stack<std::pair<int, int>>& new_bees_positions, std::vector < std::vector<int>>& bee_time) {
if (isBeeCandidate(i, j, forest)) {
forest[i][j] = 'H';
bee_time[i][j] = t;
new_bees_positions.push(std::make_pair(i, j));
}
}
std::stack<std::pair<int, int>> spreadBees(int t, std::stack<std::pair<int, int>>& current_bees_positions, std::vector<std::string>& forest, std::vector < std::vector<int>>& bee_time) {
std::stack<std::pair<int, int>> new_bees_positions;
while (!current_bees_positions.empty()) {
int current_i{ current_bees_positions.top().first };
int current_j{ current_bees_positions.top().second };
current_bees_positions.pop();
addBeeCandidate(t, current_i - 1, current_j , current_i, current_j, forest, new_bees_positions, bee_time);
addBeeCandidate(t, current_i + 1, current_j , current_i, current_j, forest, new_bees_positions, bee_time);
addBeeCandidate(t, current_i , current_j - 1, current_i, current_j, forest, new_bees_positions, bee_time);
addBeeCandidate(t, current_i , current_j + 1, current_i, current_j, forest, new_bees_positions, bee_time);
}
return new_bees_positions;
}
void addBearCandidate( int i, int j, int current_i, int current_j
, const std::vector<std::string>& forest
, std::vector<std::vector<bool>>& visited
, std::vector<std::vector<int>>& dist
, std::vector<std::vector<std::pair<int, int>>>& trajectory
, std::queue<std::pair<int,int>>& q) {
if (isBearCandidate(i, j, forest, visited)) {
q.push(std::make_pair(i, j));
visited[i][j] = true;
dist[i][j] = dist[current_i][current_j] + 1;
trajectory[i][j] = std::make_pair(current_i, current_j);
}
}
int findShortestPath(const std::vector<std::string>& forest, const std::pair<int, int>& start, const std::pair<int, int>& end) {
std::vector<std::vector<bool>> visited(N, std::vector<bool>(N, false));
std::vector<std::vector<int>> dist(N, std::vector<int>(N, 0));
std::vector<std::vector<std::pair<int, int>>> trajectory(N, std::vector<std::pair<int, int>>(N));
std::queue<std::pair<int, int>> q;
q.push(start);
int current_i{ start.first };
int current_j{ start.second };
visited[current_i][current_j] = true;
while (!q.empty() && forest[current_i][current_j] != 'D') {
current_i = q.front().first;
current_j = q.front().second;
q.pop();
if (forest[current_i][current_j] != 'D') {
addBearCandidate(current_i - 1, current_j , current_i, current_j, forest, visited, dist, trajectory, q);
addBearCandidate(current_i + 1, current_j , current_i, current_j, forest, visited, dist, trajectory, q);
addBearCandidate(current_i , current_j - 1, current_i, current_j, forest, visited, dist, trajectory, q);
addBearCandidate(current_i , current_j + 1, current_i, current_j, forest, visited, dist, trajectory, q);
}
}
/*
std::cout << dist[3][6] << std::endl;
int i{ 3 };
int j{ 6 };
while (! (i == start.first && j == start.second)) {
std::cout << trajectory[i][j].first << " " << trajectory[i][j].second << std::endl;
int temp_i{ trajectory[i][j].first };
int temp_j{ trajectory[i][j].second };
i = temp_i;
j = temp_j;
}
*/
return dist[end.first][end.second];
}
int timeToHome(int pathLength) {
int time { pathLength / S };
if (pathLength % S != 0)
++time;
return time;
}
void parser(std::vector<std::string>& forest) {
std::cin >> N >> S;
for (int i = 0; i < N; ++i) {
std::string row;
std::cin >> row;
forest.push_back(row);
}
}
void getPositions(std::vector<std::string>& forest, std::stack < std::pair<int, int>>& current_bees_positions, std::pair<int, int>& start, std::pair<int, int>& end) {
for (int i=0; i<N; ++i)
for (int j=0; j<N; ++j)
if (forest[i][j] == 'M') {
start.first = i;
start.second = j;
}
else if (forest[i][j] == 'D') {
end.first = i;
end.second = j;
}
else if (forest[i][j] == 'H')
current_bees_positions.push(std::make_pair(i, j));
}
void printForest(const std::vector<std::string>& forest) {
for (size_t i = 0; i < N; ++i)
std::cout << forest[i] << std::endl;
}
int main() {
std::vector<std::string> forest;
parser(forest);
std::stack < std::pair<int, int>> current_bees_positions;
std::pair<int, int> start{ 0,0 };
std::pair<int, int> end{ 0,0 };
getPositions(forest, current_bees_positions, start, end);
int dist{ 0 };
int temp_dist{ 0 };
int bees_time{ 0 };
std::vector<std::vector<int>> bee_times(N, std::vector<int>(N, 0));;
do {
temp_dist = findShortestPath(forest, start, end);
if (temp_dist != 0) {
++bees_time;
current_bees_positions = spreadBees(bees_time, current_bees_positions, forest, bee_times);
/*
printForest(forest);
std::cout << std::endl;
for (size_t i = 0; i < N; ++i) {
for (size_t j = 0; j < N; ++j)
std::cout << bee_times[i][j];
std::cout << std::endl;
}
std::cout << std::endl;
*/
dist = temp_dist;
}
} while (temp_dist !=0 );
int time{ bees_time - timeToHome(dist) };
//std::cout << "Bees time: " << bees_time << std::endl;
//std::cout << "Time to home: " << timeToHome(dist) << std::endl;
std::cout << time;
}
