Island Travels

Pista 1

Descompongamos el problema en varias partes. Primero identificaremos todas las islas y las distancias entre ellas.

Solución

Explicación

A partir de las pistas, separamos el problema en $3$ subproblemas.

Identificar todas las islas.
Encontrar las distancias entre islas.
Encontrar el mejor orden para visitar las islas.

En los ejemplos de abajo, $\texttt{grid}_{i, j} = 1$ para una celda de isla, $0$ para agua poco profunda, y $-1$ para agua profunda.

Identificar todas las islas

Como las cotas son tan bajas ( $R, C \leq 50$ ), podemos hacer flood fill y etiquetar cada celda de isla con un número de isla único.

C++


vector<vector<int>> comp(n, vector<int>(m, -1));
 
int comp_number = 0;
auto identify = [&](int i, int j) {
	queue<pair<int, int>> todo;
	todo.push({i, j});
 
	while (!todo.empty()) {
		pair<int, int> top = todo.front();
		todo.pop();
 
		comp[top.first][top.second] = comp_number;
 
		for (int d = 0; d < 4; d++) {
			int ni = top.first + dx[d], nj = top.second + dy[d];
 
			if (ni < 0 || ni >= n || nj < 0 || nj >= m) continue;
 
			// parte de la misma componente
			if (grid[ni][nj] == 1 && comp[ni][nj] == -1) { todo.push({ni, nj}); }
		}
	}
};
 
// visitar todas las islas
for (int i = 0; i < n; i++) {
	for (int j = 0; j < m; j++) {
		if (grid[i][j] == 1 && comp[i][j] == -1) {
			identify(i, j);
			comp_number++;
		}
	}
}

Encontrar las distancias entre islas.

Una vez más, podemos permitirnos recorrer toda la grilla para cada isla.

Hacemos un BFS 0-1 desde cada isla, esta vez permitiéndonos entrar a celdas con agua poco profunda.

C++


// cost[i][j] = distancia entre la isla i y la isla j
vector<vector<int>> cost(comp_number, vector<int>(comp_number, INF));
for (int to = 0; to < comp_number; to++) {
	// BFS 0-1 estándar
	deque<pair<int, int>> todo;
 
	vector<vector<int>> dist(n, vector<int>(m, INF));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (comp[i][j] == to) {
				todo.push_back({i, j});
				dist[i][j] = 0;
			}
		}
	}
 
	while (!todo.empty()) {
		auto top = todo.front();
		todo.pop_front();
 
		for (int d = 0; d < 4; d++) {
			int nx = top.first + dx[d], ny = top.second + dy[d];
 
			if (nx < 0 || nx >= n || ny < 0 || ny >= m || grid[nx][ny] == -1) continue;
 
			// aumentar la distancia si cruzamos agua poco profunda
			int ncost = dist[top.first][top.second] + (grid[nx][ny] == 0);
 
			if (ncost < dist[nx][ny]) {
				dist[nx][ny] = ncost;
 
				if (grid[nx][ny] == 0) todo.push_back({nx, ny});
				else todo.push_front({nx, ny});
			}
		}
	}
 
	for (int target = 0; target < comp_number; target++) {
		int best = INF;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (comp[i][j] == target) { best = min(best, dist[i][j]); }
			}
		}
 
		cost[to][target] = best;
	}
}

Encontrar el mejor orden para visitar las islas.

Notemos que la cota sobre islas ( $N$ ) es $\leq 15$ , así que podemos iterar sobre todos los subconjuntos de islas ( $2^{15} \le 10^6$ ).

Usaremos un estado de DP donde $\texttt{dp}[\texttt{mask}][i] =$ el costo mínimo tal que ya visitamos los bits encendidos en $\texttt{mask}$ y terminamos en la isla $i$ .

Podemos transicionar sobre el último paso de forma naive en $\mathcal{O}(N^2)$ , lo cual todavía entra en el límite de tiempo.

Nuestra respuesta es el elemento mínimo de $\texttt{dp}[2^n - 1]$ .

C++


// ans[mask][i] = costo mínimo si visitamos mask y estamos actualmente en i
vector<vector<int>> ans(1 << comp_number, vector<int>(comp_number, INF));
 
for (int i = 0; i < comp_number; i++) { ans[1 << i][i] = 0; }
 
for (int mask = 0; mask < (1 << comp_number); mask++) {
	for (int to = 0; to < comp_number; to++) {
		if (mask & (1 << to)) {
			for (int from = 0; from < comp_number; from++) {
				if (mask & (1 << from)) {
					ans[mask][to] = min(ans[mask][to],
					                    ans[mask ^ (1 << to)][from] + cost[from][to]);
				}
			}
		}
	}
}
 
cout << *min_element(ans[(1 << comp_number) - 1].begin(),
                     ans[(1 << comp_number) - 1].end())
     << endl;

Implementación

Después de esto, solo queda juntarlo todo.

Complejidad temporal: $\mathcal{O}(N^2 \cdot 2^N)$

C++


#include <bits/stdc++.h>
using namespace std;
 
// vectores de dirección
const vector<int> dx = {1, 0, -1, 0}, dy = {0, 1, 0, -1};
// arbitrariamente grande
const int INF = 1e9;
 
int main() {
	freopen("island.in", "r", stdin);
	freopen("island.out", "w", stdout);
 
	int n, m;
	cin >> n >> m;
 
	vector<vector<int>> grid(n, vector<int>(m));
	for (int i = 0; i < n; i++) {
		string s;
		cin >> s;
		for (int j = 0; j < m; j++) {
			if (s[j] == 'X') {
				grid[i][j] = 1;
			} else if (s[j] == 'S') {
				grid[i][j] = 0;
			} else {
				grid[i][j] = -1;
			}
		}
	}
 
	// comp[i][j] = número de isla de (i, j)
	vector<vector<int>> comp(n, vector<int>(m, -1));
 
	int comp_number = 0;
	auto identify = [&](int i, int j) {
		queue<pair<int, int>> todo;
		todo.push({i, j});
 
		while (!todo.empty()) {
			pair<int, int> top = todo.front();
			todo.pop();
 
			comp[top.first][top.second] = comp_number;
 
			for (int d = 0; d < 4; d++) {
				int ni = top.first + dx[d], nj = top.second + dy[d];
 
				if (ni < 0 || ni >= n || nj < 0 || nj >= m) continue;
 
				// parte de la misma componente
				if (grid[ni][nj] == 1 && comp[ni][nj] == -1) { todo.push({ni, nj}); }
			}
		}
	};
 
	// visitar todas las islas
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (grid[i][j] == 1 && comp[i][j] == -1) {
				identify(i, j);
				comp_number++;
			}
		}
	}
 
	// cost[i][j] = distancia entre la isla i y la isla j
	vector<vector<int>> cost(comp_number, vector<int>(comp_number, INF));
	for (int to = 0; to < comp_number; to++) {
		// BFS 0-1 estándar
		deque<pair<int, int>> todo;
 
		vector<vector<int>> dist(n, vector<int>(m, INF));
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (comp[i][j] == to) {
					todo.push_back({i, j});
					dist[i][j] = 0;
				}
			}
		}
 
		while (!todo.empty()) {
			auto top = todo.front();
			todo.pop_front();
 
			for (int d = 0; d < 4; d++) {
				int nx = top.first + dx[d], ny = top.second + dy[d];
 
				if (nx < 0 || nx >= n || ny < 0 || ny >= m || grid[nx][ny] == -1)
					continue;
 
				// aumentar la distancia si cruzamos agua poco profunda
				int ncost = dist[top.first][top.second] + (grid[nx][ny] == 0);
 
				if (ncost < dist[nx][ny]) {
					dist[nx][ny] = ncost;
 
					if (grid[nx][ny] == 0) todo.push_back({nx, ny});
					else todo.push_front({nx, ny});
				}
			}
		}
 
		for (int target = 0; target < comp_number; target++) {
			int best = INF;
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < m; j++) {
					if (comp[i][j] == target) { best = min(best, dist[i][j]); }
				}
			}
 
			cost[to][target] = best;
		}
	}
 
	// ans[mask][i] = costo mínimo si visitamos mask y estamos actualmente en i
	vector<vector<int>> ans(1 << comp_number, vector<int>(comp_number, INF));
 
	for (int i = 0; i < comp_number; i++) { ans[1 << i][i] = 0; }
 
	for (int mask = 0; mask < (1 << comp_number); mask++) {
		for (int to = 0; to < comp_number; to++) {
			if (mask & (1 << to)) {
				for (int from = 0; from < comp_number; from++) {
					if (mask & (1 << from)) {
						ans[mask][to] = min(ans[mask][to], ans[mask ^ (1 << to)][from] +
						                                       cost[from][to]);
					}
				}
			}
		}
	}
	cout << *min_element(ans[(1 << comp_number) - 1].begin(),
	                     ans[(1 << comp_number) - 1].end())
	     << endl;
}