Fort Moo

Solución

Explicación

Al calcular las sumas de prefijos 2D de la grilla, podemos evaluar la usabilidad de un marco en tiempo $\mathcal{O}(1)$ .

Debido a las cotas bajas de $N$ , podemos iterar sobre todos los pares posibles de columnas y encontrar el marco de área máxima en $O(N)$ con una ventana deslizante.

Implementación

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

C++


#include <bits/stdc++.h>
using namespace std;
 
int main() {
	freopen("fortmoo.in", "r", stdin);
	freopen("fortmoo.out", "w", stdout);
 
	int n, m;
	cin >> n >> m;
 
	vector<vector<bool>> grid(n, vector<bool>(m));
	vector<vector<int>> pref_sum(n + 1, vector<int>(m + 1));
 
	for (int i = 0; i < n; i++) {
		string s;
		cin >> s;
 
		for (int j = 0; j < m; j++) {
			grid[i][j] = s[j] == 'X';
 
			// construir suma de prefijos
			pref_sum[i + 1][j + 1] = pref_sum[i][j + 1] + pref_sum[i + 1][j];
			pref_sum[i + 1][j + 1] -= pref_sum[i][j];
			pref_sum[i + 1][j + 1] += grid[i][j];
		}
	}
 
	int max_area = 0;
 
	for (int c1 = 0; c1 < m; c1++) {
		for (int c2 = 0; c2 < m; c2++) {
			int prev = -1;
 
			for (int r = 0; r < n; r++) {
				bool emp = (pref_sum[r + 1][c2 + 1] - pref_sum[r][c2 + 1] -
				            pref_sum[r + 1][c1] + pref_sum[r][c1]) == 0;
 
				// solo fila
				if (emp) { max_area = max(max_area, c2 - c1 + 1); }
 
				// podemos continuar a partir de una fila válida anterior
				if (emp && prev != -1) {
					// actualizar respuesta
					max_area = max(max_area, (r - prev + 1) * (c2 - c1 + 1));
				}
 
				// reiniciar prev
				if (grid[r][c1] || grid[r][c2]) { prev = -1; }
 
				// asignar prev
				if (emp && prev == -1) { prev = r; }
			}
		}
	}
 
	cout << max_area << endl;
}

Solución alternativa

Explicación

El enfoque aquí es un poco distinto al de la solución oficial, usando una adaptación del algoritmo de Kadane 2D.

Iteramos sobre todos los pares posibles de columnas. Para cada par, resolveremos el problema con la restricción de que el fuerte debe estar alineado a lo largo de estas dos columnas. Para cada fila entre estas dos columnas, usaremos sumas de prefijos para comprobar si el área entre las dos columnas y en la fila está despejada.

Mantenemos una variable acumulada $r_{start}$ que lleva la cuenta de la fila más temprana en la que podemos empezar el fuerte e iteramos sobre todos los finales de fila posibles ( $r_{end}$ en el código). Notemos que si un área pantanosa reside en una de las columnas mismas, ningún fuerte puede pasar por esa fila, así que debemos comprobarlo y actualizar $r_{start}$ en consecuencia.

Implementación

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

C++Java


#include <algorithm>
#include <fstream>
#include <iostream>
#include <vector>
 
using std::cout;
using std::endl;
using std::vector;
 
const char BAD = 'X';
 
// 2016 jan plat
int main() {
	std::ifstream read("fortmoo.in");
	int row_num;
	int col_num;
	read >> row_num >> col_num;
 
	vector<vector<bool>> sturdy(row_num, vector<bool>(col_num));
	// col_num + 1 por cómo funcionan las sumas de prefijos
	vector<vector<int>> row_bad_nums(row_num, vector<int>(col_num + 1));
	for (int r = 0; r < row_num; r++) {
		for (int c = 0; c < col_num; c++) {
			char cell;
			read >> cell;
			sturdy[r][c] = cell != BAD;
			row_bad_nums[r][c + 1] += row_bad_nums[r][c] + (cell == BAD);
		}
	}
 
	int max_area = 0;
	for (int c_start = 0; c_start < col_num; c_start++) {
		for (int c_end = c_start + 1; c_end < col_num; c_end++) {
			int r_start = 0;
			for (int r_end = 0; r_end < row_num; r_end++) {
				bool rowValid =
				    row_bad_nums[r_end][c_end + 1] - row_bad_nums[r_end][c_start] == 0;
				if (r_end == r_start && !rowValid) {
					r_start++;
					continue;
				}
				if (!sturdy[r_end][c_start] || !sturdy[r_end][c_end]) {
					r_start = r_end + 1;
				} else if (rowValid && r_start != r_end) {
					max_area = std::max(max_area,
					                    (c_end - c_start + 1) * (r_end - r_start + 1));
				}
			}
		}
	}
	cout << max_area << endl;
	std::ofstream("fortmoo.out") << max_area << endl;
}


import java.io.*;
import java.util.*;
 
public class FortMoo {
	private static final char BAD = 'X';
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new FileReader("fortmoo.in"));
		StringTokenizer initial = new StringTokenizer(read.readLine());
		int rowNum = Integer.parseInt(initial.nextToken());
		int colNum = Integer.parseInt(initial.nextToken());
 
		boolean[][] sturdy = new boolean[rowNum][colNum];
		// colNum + 1 por cómo funcionan las sumas de prefijos
		int[][] rowBadNums = new int[rowNum][colNum + 1];
		for (int r = 0; r < rowNum; r++) {
			String row = read.readLine();
			for (int c = 0; c < colNum; c++) {
				rowBadNums[r][c + 1] =
				    rowBadNums[r][c] + (row.charAt(c) == BAD ? 1 : 0);
				sturdy[r][c] = row.charAt(c) != BAD;
			}
		}
 
		int maxArea = 0;
		for (int cStart = 0; cStart < colNum; cStart++) {
			for (int cEnd = cStart + 1; cEnd < colNum; cEnd++) {
				int rStart = 0;
				for (int rEnd = 0; rEnd < rowNum; rEnd++) {
					boolean rowValid =
					    rowBadNums[rEnd][cEnd + 1] - rowBadNums[rEnd][cStart] == 0;
					if (rEnd == rStart && !rowValid) {
						rStart++;
						continue;
					}
					if (!sturdy[rEnd][cStart] || !sturdy[rEnd][cEnd]) {
						rStart = rEnd + 1;
					} else if (rowValid && rStart != rEnd) {
						maxArea = Math.max(maxArea,
						                   (cEnd - cStart + 1) * (rEnd - rStart + 1));
					}
				}
			}
		}
 
		PrintWriter written = new PrintWriter("fortmoo.out");
		written.println(maxArea);
		written.close();
		System.out.println(maxArea);
	}
}