Úloha: Kamenná deska

Jistá kamenická firma řeší následující problém. Na skladě má veliké desky mramoru jednotné tloušťky. Problém je v tom, že barevná struktura mramoru není všude stejná a místy jsou desky poškozené. Aby bylo možné mramorové desky výhodně prodávat, je třeba je rozřezat na co do objemu největší kvádry, které mají stejnou barevnou strukturu a nejsou nikde poškozené. Struktura mramorové desky je zadána maticí, kde každá buňka obsahuje informaci o své barevné struktuře nebo o tom, zda je poškozená. Barevná struktura je označena celým kladným číslem v rozsahu 1 až 1023. Poškozená buňka je označena nulou. Napište program, který najde pro zadanou kamennou desku maximální obdélník, který nemá uvnitř žádné poškození a má jednotnou barevnou strukturu. Maximálním obdélníkem se myslí submatice obsahující maximální množství buněk. Pokud existuje více řešení, vypište libovolné z nich.

Vstup:

Ve vstupním souboru je na prvním řádku uveden počet řádků matice a na druhém řádku počet sloupců matice. Další řádky obsahují vlastní matici tak, že jeden řádek vstupu je jeden řádek matice. Čísla na řádcích jsou oddělena mezerami.

Výstup:

Na prvním řádku je číslo udávající počet buněk hledané submatice. Pokud taková submatice neexistuje, je tento řádek jediný a obsahuje nulu. Na dalším řádku je čtveřice čísel oddělených mezerami. První číslo přestavuje číslo řádku (číslováno od 1) levého horního rohu hledané submatice. Druhé číslo přestavuje číslo sloupce (číslováno od 1) levého horního rohu hledané submatice. Třetí číslo přestavuje číslo řádku (číslováno od 1) pravého dolního rohu hledané submatice. Čtvrté číslo přestavuje číslo sloupce (číslováno od 1) pravého dolního rohu hledané submatice.

Příklad: