#include #include #include #include int main() { // Dimensionen der Fläche einlesen int width, height; scanf("%d %d\n", &width, &height); // Fläche einlesen int *sum = (int *)malloc((height + 1) * (width + 1) * sizeof(int)); memset(sum, 0, (height + 1) * (width + 1) * sizeof(int)); for (int i = 1; i <= height; i++) { for (int j = 1; j <= width; j++) { int current_value = (getchar() == '#') ? 1 : 0; sum[i * (width + 1) + j] = current_value + sum[(i - 1) * (width + 1) + j] + sum[i * (width + 1) + j - 1] - sum[(i - 1) * (width + 1) + j - 1]; } // Newline ignorieren getchar(); } // Noch keine passende Fläche gefunden, deshalb mit -1 vorbelegt int solution_x = -1, solution_y = -1, solution_w = -1, solution_h = -1; bool solution_found = false; // Durch alle Zeilen iterieren (y-Koordinate) for (int start_y = 1; start_y <= height; start_y++) { // Durch alle Spalten iterieren (x-Koordinate) for (int start_x = 1; start_x <= width; start_x++) { // Alle möglichen Höhen versuchen, beginnend bei der kleinsten for (int end_y = start_y; end_y <= height; end_y++) { // Alle möglichen Breiten versuchen, beginnend bei der kleinsten for (int end_x = start_x; end_x <= width; end_x++) { // Hindernisse im ausgewählten Bereich berechnen unsigned int num_window_obstacles = sum[end_y * (width + 1) + end_x] - sum[end_y * (width + 1) + start_x - 1] - sum[(start_y - 1) * (width + 1) + end_x] + sum[(start_y - 1) * (width + 1) + start_x - 1]; // Überprüfen, ob in dem Bereich Hindernisse gefunden wurden if (num_window_obstacles == 0) { // Prüfen, ob das neue Feld größer ist als das bisher // größte gefundene. Gegebenenfalls Koordinaten und // Größe speichern. int candidate_w = end_x - start_x + 1; int candidate_h = end_y - start_y + 1; if (!solution_found || (candidate_w * candidate_h) > (solution_w * solution_h)) { solution_found = true; solution_x = start_x - 1; solution_y = start_y - 1; solution_w = candidate_w; solution_h = candidate_h; } } else { // Die Schleifen verkleinern die zu überprüfende Fläche. // In der innersten Schleife kann somit keine größere Fläche // mehr gefunden werden. break; } } } } } // Ergebnis ausgeben if (solution_found) printf("x: %d y: %d w: %d h: %d -> %d\n", solution_x, solution_y, solution_w, solution_h, solution_w * solution_h); else printf("Keine freie Flaeche gefunden"); return 0; }