[71104]

per il punto 1 io direi un programmazione dinamica rapidissimo

detta m la matrice di input, la formula ricorsiva è:

OPT(x, y) = 1 + min{OPT(x+1, y), OPT(x, y+1), OPT(x+1, y+1)} se m[x,y] è uguale a 0

OPT(x, y) = 0 se m[x,y] è diverso da 0


in questo modo OPT(x, y) trova il lato della sottomatrice quadrata più grossa. in quest'ottica la matrice ausiliaria è a due dimensioni e contiene in ciascuna cella il lato della massima sottomatrice nulla "radicata" a quelle coordinate. per avere, oltre alla misura del lato, le coordinate d'origine della sottomatrice cercata si potrebbe fare una ricerca nella matrice ausiliaria, cosa che richiederebbe O(N*M) e che quindi non aumenterebbe la complessità dell'algoritmo, ma sarebbe ovviamente una sciocchezza dopo aver fatto tanto lavoro per cercare il lato
piuttosto sarebbe meglio pensare ad una modifica all'algoritmo risultante affinché restituisca le coordinate anziché il lato.

intanto, detta t la matrice ausiliaria che si suppone inizializzata interamente a -1, e dette N ed M le dimensioni della matrice di input, questo è l'algoritmo che restituisce il lato, in pseudocodice:

function f(x, y)
	if m[x, y] != 0
		t[x, y] <- 0
	else
		if x <= N
			if t[x+1, y] == -1
				t[x+1, y] <- f(x+1, y)
		if y <= M
			if t[x, y+1] == -1
				t[x, y+1] <- f(x, y+1)
		if (x <= N) and (y <= M)
			if t[x+1, y+1] == -1
				t[x+1, y+1] <- f(x+1, y+1)
		t[x, y] <- 1 + min{t[x+1, y], t[x, y+1], t[x+1, y+1]}
	return t[x, y]

e questo è l'algoritmo modificato che restituisce anche le coordinate, inventato or ora:

#bestX e bestY sono due variabili globali entrambe inizializzate a -1

function f(x, y)
	if m[x, y] != 0
		t[x, y] <- 0
	else
		if x <= N
			if t[x+1, y] == -1
				t[x+1, y] <- f(x+1, y)
		if y <= M
			if t[x, y+1] == -1
				t[x, y+1] <- f(x, y+1)
		if (x <= N) and (y <= M)
			if t[x+1, y+1] == -1
				t[x+1, y+1] <- f(x+1, y+1)
		t[x, y] <- 1 + min{t[x+1, y], t[x, y+1], t[x+1, y+1]}
		if t[x, y] > t[bestX, bestY]
			bestX <- x
			bestY <- y
	return t[x, y]

#se al termine dell'algoritmo bestX e bestY valgono ancora -1 e -1 significa che la matrice non contiene zeri

quando ho tempo provo a scriverne un'implementazione. comunque, per chiarezza, la complessità di questa versione dovrebbe essere O(N*M), cioè la funzione viene chiamata al massimo N per M volte.


edit - argh, preceduto da marco.r