Matura 2019 - działki

Witam!

Mam problem z ostatnim podpunktem zadania nr 4 maturalnego ze starej formuły 2019.
Link do arkusza: link
Link do danych: link

Polecenie: W rogu północno-zachodnim działki (czyli lewym górnym rogu mapy) trzeba wytyczyć kwadratowy plac, który nie może zawierać przeszkód terenowych (czyli zawiera wyłącznie pola puste oraz trawiaste). Znajdź działkę, na której zmieści się taki plac o największej powierzchni. Jako odpowiedź podaj numer tej działki oraz długość boku placu. Jeśli jest więcej takich działek, podaj numery ich wszystkich. Przykładowo z podanego rysunku można wytyczyć kwadratowy plac o boku o długości 4. Dla pliku przyklad.txt odpowiedź to: numer działki – 4, maksymalny bok – 7.

Podzieliłem dane na działki, działki jeszcze na poszczególne linie i przygotowałem pętle by przechodziły przez range(0,15) linii w działce i range(0,15) znaków w poszczególnej linii (warunek górnego lewego roku). Nie wiem jednak jak zabrać się za warunek główny, czyli to żeby wyznaczyć największy możliwy kwadrat.

Musisz po prostu znaleźć pierwszą kolumnę i pierwszy wiersz (licząc od tego twojego rogu), który zawiera przeszkodę i wybrać mniejszą z tych wartości jako bok kwadratu. Jak nie obchodzi cię złożoność, to możesz to zrobić przeglądając raz całą tablicę i szukając przeszkody o współrzednych najbliżej twojego rogu. Jak chcesz optymalizować, to najlepiej wystartować z tego rogu i przeglądać sobie najpierw wszystkie pola odległe od rogu o 1, następnie odległe o 2, następnie o 3 itd:

.*
**

..*
..*
***

...*
...*
...*
****

I jak trafiasz na przeszkodę to w takiej odległości w jakiej na nią tafiłeś, taki masz bok kwadratu.

Shalom napisał(a):

Musisz po prostu znaleźć pierwszą kolumnę i pierwszy wiersz (licząc od tego twojego rogu), który zawiera przeszkodę i wybrać mniejszą z tych wartości jako bok kwadratu. Jak nie obchodzi cię złożoność, to możesz to zrobić przeglądając raz całą tablicę i szukając przeszkody o współrzednych najbliżej twojego rogu. Jak chcesz optymalizować, to najlepiej wystartować z tego rogu i przeglądać sobie najpierw wszystkie pola odległe od rogu o 1, następnie odległe o 2, następnie o 3 itd:

.*
**

..*
..*
***

...*
...*
...*
****

I jak trafiasz na przeszkodę to w takiej odległości w jakiej na nią tafiłeś, taki masz bok kwadratu.

wspolrzedne_y=[]
wspolrzedne_x=[]

for dzialka in dane_4_3:

    for y in range(0, 15):
        for x in range(0,15):
            if dzialka[y][x]=='X':
                wspolrzedne_y.append(y)
                wspolrzedne_x.append(x)

    dlugosci_y = []
    dlugosci_x = []

    for wspolrzedna_y in wspolrzedne_y:
        dlugosci_y.append(wspolrzedna_y)

    for wspolrzedna_x in wspolrzedne_x:
        dlugosci_x.append(wspolrzedna_x)


    najw_pole = []

    for i in range(len(dlugosci_x)):
        if dlugosci_y[i] == dlugosci_x[i]:
            najw_pole.append(dlugosci_x[i] * dlugosci_y[i])
        else:
            najw_pole.append(pow(min(dlugosci_y[i],dlugosci_x[i]),2))




print(max(najw_pole))

Mam taki kod, ale niestety maksymalne pole wychodzi 196 a nie 144.

f=open('dzialki.txt', 'r')
dane=f.read()

dane_rozdzielone = dane.split("\n\n")

dane_4_3=[]
for linia in dane_rozdzielone:
    rozdzielona_linia=linia.split('\n')
    dane_4_3.append(rozdzielona_linia)


pola_kwadratów=[]

for dzialka in dane_4_3:
    czy_break=False

    for i in range(len(dzialka)):
        punkt_odleglosci=dzialka[i][i]


        for j in range(0,i):
            if (dzialka[j][i]=="X") or (dzialka[i][j]=='X') or (punkt_odleglosci=='X'):
                pola_kwadratów.append(i**2)
                czy_break=True
                break
        if czy_break==True:
            break
    if czy_break==True:
        continue

numery_działek=[]
dlugosc_boku_najdluzszego=int((max(pola_kwadratów)))

for i in range(0, len(pola_kwadratów)):
    if pola_kwadratów[i]==dlugosc_boku_najdluzszego:
        numery_działek.append(i+1)


print("Wynik: " + str(int((max(pola_kwadratów))**(1/2))))
print("Numery działek: " + str(numery_działek))

Wiem, że kod nie jest optymalny, ale to jedyne na co mnie obecnie już dzisiaj stać.

To jakby ktoś kiedyś szukał rozwiązania tego zadania to podsyłam kod, napisane w C++. Rozwiązanie trochę armatka, bo wykorzystujące sumy prefiksowe 2D. Po wczytaniu program wylicza tablicę dwuwymiarową pref, gdzie pref[i][j] > 0 oznacza, że na prostokącie zaczynającym się w lewym górnym rogu i kończącym się w pkt o współrzędnych (i, j) jest jakaś przeszkoda. Po wyliczeniu tej tablicy wystarczy się przelecieć po szukanej długości boku (najlepiej to wybinserzczować ten wynik) i znaleźć wynik. Kod:

#include <bits/stdc++.h>

using namespace std;

#define LL long long 
#define ULL unsigned LL
#define LD long double

string s[30];

int solve() {
	int pref[31][31];
	for(int i=0; i<=30; i++)
		pref[i][0] = 0;
	for(int i=0; i<=30; i++)
		pref[0][i] = 0;
	for(int i=1; i<=30; i++) {
		for(int j=1; j<=30; j++) {
			if(s[i-1][j-1] != '.')
				pref[i][j] = pref[i-1][j] + pref[i][j-1] - pref[i-1][j-1] + 1;
			else
				pref[i][j] = pref[i-1][j] + pref[i][j-1] - pref[i-1][j-1];
		}
	}
	for(int i=1; i<=31; i++) {
		if(i==31)
			return i-1;
		if(pref[i][i])
			return i-1;
	}
}

int main() {
	fstream in, out;
	in.open("dzialki.txt", ios::in);
	out.open("wynik.txt", ios::out);
	int w = 0;
	int kt = 0;
	for(int i=0; i<50; i++) {
		for(int j=0; j<30; j++)
			getline(in, s[j]);
		string r;
		getline(in, r);
		int wx = solve();
		if(wx > w) {
			w = wx;
			kt = i+1;
		}
	}
	out<<"Numer dzialki: "<<kt<<", wynik = "<<w;
}