Skip to Content
CTRL K

Mecho

Análisis oficial 

Explicación

Asumiendo que Mecho puede llegar a su cueva antes que las abejas, está garantizado que Mecho puede hacerlo si come durante cualquier tiempo entre 0 y xx. Cualquier tiempo mayor que xx permitiría que las abejas atrapen a Mecho.

A partir de esta observación, vemos que podemos hacer búsqueda binaria sobre el tiempo de comida para hallar el último instante posible en que Mecho puede partir. Para el tiempo xx, que es la cantidad de tiempo que Mecho come, comprobamos si Mecho puede llegar a su cueva antes que las abejas. Si puede, entonces buscamos binariamente en tiempos mayores que xx; si no, buscamos binariamente en tiempos menores que xx. Hacemos esto hasta que quede un único tiempo de comida. Para ver si Mecho puede llegar a su cueva antes que las abejas, necesita tener un camino en el que cada casilla sea un parche de pasto y sea alcanzable por Mecho antes que las abejas.

Ejecutamos un BFS para las abejas y registramos el tiempo que tardan en llegar a cada nodo posible del grafo. Luego ejecutamos otro BFS para Mecho, donde un nodo solo será visitado por Mecho si es un parche de pasto y las abejas tardaron más tiempo en llegar al nodo que Mecho. Si se cumplen ambas condiciones, podemos decir que Mecho llegó al nodo antes que las abejas. Al final del BFS, comprobamos si Mecho llegó a alguno de los cuatro nodos que rodean su cueva. Si lo hizo, entonces Mecho llegó con éxito a la cueva comiendo durante xx tiempo. En caso contrario, Mecho tendrá que comer durante menos de xx tiempo.

Imprimimos el máximo tiempo de espera hallado por la búsqueda binaria. Si Mecho no puede llegar a la cueva ni siquiera cuando come durante 0 unidades de tiempo, entonces no hay camino desde su posición inicial hasta la cueva. En este caso, imprimimos −1-1.

Implementación

Complejidad temporal: O(N2log⁡N)\mathcal{O}(N^2\log N)

#include <bits/stdc++.h>
using namespace std;
 
const int MAX_N = 800;
vector<string> field(MAX_N);
int n, s;
 
bool valid_sq(int x, int y) {
	return x >= 0 && x < n && y >= 0 && y < n &&
	       (field[x][y] == 'G' || field[x][y] == 'M');
}
 
bool mecho_reached(int mecho_dis, int bees_dis) { return mecho_dis / s < bees_dis; }
 
int main() {
	cin >> n >> s;
	for (int i = 0; i < n; i++) { cin >> field[i]; }
 
	vector<pair<int, int>> hives;
	int mechox, mechoy, home_x, home_y;
	// hallamos las coordenadas x e y de Mecho, las abejas y la cueva
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (field[i][j] == 'M') {
				mechox = i;
				mechoy = j;
			} else if (field[i][j] == 'H') {
				hives.push_back({i, j});
			} else if (field[i][j] == 'D') {
				home_x = i;
				home_y = j;
			}
		}
	}
 
	int dx[] = {-1, 0, 1, 0};
	int dy[] = {0, -1, 0, 1};
 
	// búsqueda binaria sobre el tiempo de espera
	int l = 0;
	int r = n * n;
	while (l <= r) {
		vector<vector<bool>> bees_visited(n, vector<bool>(n));
		vector<vector<bool>> mecho_visited(n, vector<bool>(n));
		vector<vector<int>> bees_time(n, vector<int>(n));
		vector<vector<int>> mecho_time(n, vector<int>(n));
		queue<pair<int, int>> q;
 
		int eating_time = (l + r) / 2;
 
		// movemos a las abejas
		for (auto i : hives) {
			q.push({i.first, i.second});
			bees_visited[i.first][i.second] = true;
		}
 
		while (!q.empty()) {
			int x = q.front().first, y = q.front().second;
			q.pop();
			for (int i = 0; i < 4; i++) {
				int nx = x + dx[i], ny = y + dy[i];
				if (valid_sq(nx, ny) && !bees_visited[nx][ny]) {
					bees_time[nx][ny] = bees_time[x][y] + 1;
					q.push({nx, ny});
					bees_visited[nx][ny] = true;
				}
			}
		}
 
		// movemos a Mecho
		q.push({mechox, mechoy});
		mecho_visited[mechox][mechoy] = true;
		if (bees_time[mechox][mechoy] <= eating_time) { q.pop(); }
 
		while (!q.empty()) {
			int x = q.front().first, y = q.front().second;
			q.pop();
			for (int i = 0; i < 4; i++) {
				int nx = x + dx[i], ny = y + dy[i];
				/*
				 * comprobamos si Mecho llega al nodo[x][y] antes que las abejas
				 * dividimos el tiempo que Mecho tarda en llegar a un nodo por s, ya que
				 * Mecho camina s pasos a la vez.
				 * restamos el tiempo de comida del tiempo que tardan las
				 * abejas en llegar al nodo, porque ese tiempo lo usó
				 * Mecho para comer
				 */
				if (valid_sq(nx, ny) && !mecho_visited[nx][ny] &&
				    mecho_reached(mecho_time[x][y] + 1,
				                  bees_time[nx][ny] - eating_time)) {
					mecho_visited[nx][ny] = true;
					q.push({nx, ny});
					mecho_time[nx][ny] = mecho_time[x][y] + 1;
				}
			}
		}
 
		// comprobamos si Mecho llegó a un nodo que rodea su cueva antes que las abejas
		bool reached = false;
		for (int i = 0; i < 4; i++) {
			int nx = home_x + dx[i], ny = home_y + dy[i];
			if (valid_sq(nx, ny) &&
			    mecho_reached(mecho_time[nx][ny], bees_time[nx][ny] - eating_time) &&
			    mecho_visited[nx][ny]) {
				reached = true;
			}
		}
		if (reached) {
			l = eating_time + 1;
		} else {
			r = eating_time - 1;
		}
	}
 
	cout << l - 1 << '\n';
}
Fundamentos