#include #include #include const char OBSTACLE_CHARACTER = '#'; int main() { // Dimensionen des Grundstücks einlesen int width, height; scanf("%d %d\n", &width, &height); // Grundstücks einlesen char *area = (char *)malloc(width * height * sizeof(char)); for (int i = 0; i < height; i++) { for (int j = 0; j < width; j++) area[i * width + j] = getchar(); // 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 = 0; start_y < height; start_y++) { // Durch alle Spalten iterieren (x-Koordinate) for (int start_x = 0; 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 zählen unsigned int num_window_obstacles = 0; for (int window_y = start_y; window_y <= end_y && num_window_obstacles == 0; window_y++) { for (int window_x = start_x; window_x <= end_x && num_window_obstacles == 0; window_x++) { if(area[window_y * width + window_x] == OBSTACLE_CHARACTER) num_window_obstacles++; } } // Ü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; solution_y = start_y; 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"); free(area); return 0; }