Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
USACO FALL '97.
Përkthyer nga: Kamila Hasanbega
PROBLEM 4: Hangari i madh[USACO FALL '97]
Fermeri John do që të vendosë hangarin e tij
të madh katror në fermën e tij me formë katrore.
Atij nuk i pëlqen që ti presë pemët ndaj duhet që
të gjejë një vend ku nuk ka pemë për ta vendosur.
Ferma e tij ndahet në parcela NxN. Inputi përfshin
lisën e parcelave që pembajnë këto pemë. Puna juaj
është që të zbuloni hangarin më të
madh katror që mund të vendoset pa i prerë pemët.
Anët e hangarit duhet të jenë paralele me boshtin
vertical ose horizontal.
SHEMBULL:
Konsideroni skemën e mëposhtme të fermës se
John ku ' . ' përfaqëson një parcelë pa pemë dhe
'#' përfaqëson një parcelë me pemë:
1 2 3 4 5 6 7 8
1 . . . . . . . .
2 . # . . . # . .
3 . . . . . . . .
4 . . . . . . . .
5 . . . . . . . .
6 . . # . . . . .
7 . . . . . . . .
8 . . . . . . . .
Hambar me i madh është 5 x 5 dhe mund të vendoset në njërin prej dy vendeve në pjesën e poshtme të djathtë të skemës.
FORMATI I INPUT-IT
| Reshti 1: |
Dy numra të plotë : N (1 <= N <= 250), numri i parcelave në një anë, dhe T (1 <= T <= 600) numri i parcelave me pemë. |
| Reshti 2..T+1: |
2 numra të plotë (1 <= cdo numër <= N), rreshtat dhe kolonat e parcelave në një pemë. |
SHEMBULL INPUT (file INPUT.TXT): 8 3
2 2
2 6
6 3
FORMATI I OUTPUT-IT
File i output-it konsiston nga një rresht, gjatësia maksimale e anës se hangarit të fermerit John.
SHEMBULL OUTPUT (file OUTPUT.TXT): 5
Для отправки решений необходимо выполнить вход.
|