Entrada
La entrada consiste en múltiples conjuntos de datos. Cada conjunto comienza con dos enteros, W y H, que representan el ancho y alto de la cuadrícula, respectivamente (ambos no exceden 20). A continuación, se presentan H líneas, cada una con W caracteres que definen el color de las baldosas:
.: Baldosa negra.#: Baldosa roja.@: Baldosa negra de inicio (aparece una vez por conjunto de datos).
La entrada finaliza cuando se leen W=0 y H=0.
Salida
Para cada conjunto de datos, se debe imprimir una línea con el número total de baldosas negras accesibles desde la posición inicial.
Ejemplo de Entrada
6 9
....#.
.....#
......
......
......
......
......
#@...#
.#..#.
0 0
Ejemplo de Salida
45
Análisis del Problema
El núcleo de este problema es identificar y contar todas las celdas conectadas a la celda de inicio que cumplen con las condiciones (ser negras y adyacentes). Este es un problema clásico de encontrar el tamaño de un componente conexo en un grafo implícito, donde cada baldosa negra es un nodo y las adyacencias entre baldosas negras son las aristas. La técnica adecuada para esto es la Búsqueda en Profundidad (DFS) o la Búsqueda en Anchura (BFS). Usaremos DFS.
Implementación con DFS
Definiremos una función DFS que explore la cuadrícula recursivamente. Necesitaremos:
- Una representación de la cuadrícula (un array 2D de caracteres).
- Variables para almacenar el ancho (W) y alto (H) de la cuadrícula.
- Un contador para el número de baldosas negras alcanzadas.
- Un array 2D de booleanos (
vis) para marcar las baldosas ya visitadas y evitar ciclos o recuentos. - Arrays
dxydypara facilitar el movimiento a las celdas adyacentes (arriba, abajo, izquierda, derecha).
Función DFS (Primera Versión)
Esta versión marca la celda actual como visitada y la cuenta, luego explora sus vecinos.
#include <iostream>
#include <vector>
#include <cstring> // Para memset
char grid[21][21];
int grid_width, grid_height, reachable_count;
bool visited[21][21];
// Direcciones de movimiento: arriba, abajo, derecha, izquierda
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, 1, -1};
void dfs(int r, int c) {
visited[r][c] = true; // Marcar la celda actual como visitada
reachable_count++; // Incrementar el contador
// Explorar las 4 celdas adyacentes
for (int i = 0; i < 4; ++i) {
int next_r = r + dx[i];
int next_c = c + dy[i];
// Verificar si la celda adyacente está dentro de los límites
if (next_r < 0 || next_r >= grid_height || next_c < 0 || next_c >= grid_width) {
continue;
}
// Verificar si la celda adyacente es negra y no ha sido visitada
if (grid[next_r][next_c] == '.' && !visited[next_r][next_c]) {
dfs(next_r, next_c); // Llamada recursiva
}
}
}
int main() {
while (true) {
std::cin >> grid_width >> grid_height;
if (grid_width == 0 && grid_height == 0) {
break;
}
int start_row = -1, start_col = -1;
for (int r = 0; r < grid_height; ++r) {
// Leer la línea de la cuadrícula, ajustando para índice 0
std::string row_str;
std::cin >> row_str;
for (int c = 0; c < grid_width; ++c) {
grid[r][c] = row_str[c];
if (grid[r][c] == '@') {
start_row = r;
start_col = c;
}
}
}
// Si no se encuentra el punto de inicio '@', el resultado es 0.
// Esto puede ocurrir si la entrada es válida pero '@' está ausente.
if (start_row == -1) {
std::cout << 0 << std::endl;
continue;
}
reachable_count = 0;
// Inicializar el array de visitados para cada nuevo conjunto de datos
std::memset(visited, false, sizeof(visited));
dfs(start_row, start_col); // Iniciar la búsqueda desde el punto '@'
std::cout << reachable_count << std::endl;
}
return 0;
}
Variación de la Función DFS
Otra forma de estructurar la DFS es marcar la celda como visitada *después* de la llamada recursiva, pero esto requiere ajustar el conteo y la inicialización para asegurar que la celda de inicio se cuente correctamente.
Si modificamos la DFS para marcar y contar *dentro* del bucle de exploración, la función principal necesitará inicializar el contador a 1 (para la celda de inicio) y llamar a la DFS. Los límites de la cuadrícula se manejan de forma similar.
Código Completo con la Segunda Variación de DFS
Esta versión de DFS marca una celda *antes* de la llamada recursiva y la incrementa. La main se ajusta para inicializar el contador a 1 si se encuentra el punto de inicio.
#include <iostream>
#include <vector>
#include <cstring> // Para memset
char grid[21][21];
int grid_width, grid_height, reachable_count;
bool visited[21][21];
// Direcciones de movimiento: arriba, abajo, derecha, izquierda
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, 1, -1};
void dfs_explore(int r, int c) {
// Explorar las 4 celdas adyacentes
for (int i = 0; i < 4; ++i) {
int next_r = r + dx[i];
int next_c = c + dy[i];
// Verificar límites
if (next_r < 0 || next_r >= grid_height || next_c < 0 || next_c >= grid_width) {
continue;
}
// Si es una baldosa negra válida y no visitada
if (grid[next_r][next_c] == '.' && !visited[next_r][next_c]) {
visited[next_r][next_c] = true; // Marcar antes de la llamada
reachable_count++; // Contar
dfs_explore(next_r, next_c); // Explorar
}
}
}
int main() {
std::ios_base::sync_with_stdio(false); // Optimización de I/O
std::cin.tie(NULL);
while (true) {
std::cin >> grid_width >> grid_height;
if (grid_width == 0 && grid_height == 0) {
break;
}
int start_row = -1, start_col = -1;
for (int r = 0; r < grid_height; ++r) {
std::string row_str;
std::cin >> row_str;
for (int c = 0; c < grid_width; ++c) {
grid[r][c] = row_str[c];
if (grid[r][c] == '@') {
start_row = r;
start_col = c;
}
}
}
if (start_row == -1) {
std::cout << 0 << std::endl;
continue;
}
reachable_count = 1; // Inicializar el contador a 1 para la celda de inicio
std::memset(visited, false, sizeof(visited));
visited[start_row][start_col] = true; // Marcar la celda de inicio como visitada
dfs_explore(start_row, start_col); // Iniciar la exploración
std::cout << reachable_count << std::endl;
}
return 0;
}