Programozás‎ > ‎Feladatok‎ > ‎

A kastély

János gazda születésnapjára kaparós sorsjegyet kapott. Legnagyobb meglepetésére nyert a sorsjeggyel egy ír kastélyt. Örömét szeretné megosztani teheneivel, ezért elmesélné nekik, hogy hány szoba van a kastélyban, és melyik a legnagyobb. Sőt, ki is akarja bontani az egyik falat, hogy egy még nagyobb szobát hozzon létre.

A kastély tervrajza egy N soros  és M oszlopos táblázat. Minden mezőt 0, 1, 2, 3 vagy 4 fal határolhat. A "külső" éleken mindig fal van, hogy megvédjen a széltől és az esőtől.

Példa tervrajzra:


    1    2   3   4   5   6   7

  #############################
1 #   |   #   |   #   |   |   #
  #####---#####---#---#####---#

2 #   #   |   #   #   #   #   #
  #---#####---#####---#####---#

3 #   |   |   #   #   #   #   #
  #---#########---#####---#---#

4 # ->#   |   |   |   |   #   #
  #############################


# = fal 
-, | = nincs fal 
-> = ezt a falat kell lebontani, hogy a lehető legnagyobb szobát kapjuk meg

A fenti kastély 7 x 4 mezőből áll és öt szobát tartalmaz, amelyek mérete 9, 7, 3, 1 és 8, valamilyen sorrendben.

A nyíllal jelölt fal eltávolítása után alakul ki a legnagyobb létrehozható szoba.

Feltehetjük, hogy a kastély mindig tartalmaz legalább két szobát, és mindig van eltávolítható fal. 

A kastély kódolása

A kastély tervrajza mezőkből áll, minden mezőt egy szám kódol. N sor mindegyikében M szám áll. A mezők balról jobbra és fentről lefelé számozottak, egytől kezdődően.

Egy mezőt határoló falakat az alábbi számok összege írja le: 
  • 1: nyugati fal
  • 2: északi fal
  • 4: keleti fal
  • 8: déli fal
A belső falak kétszer vannak leírva, mindkét mezőnél, amelyeket elválasztanak.

Feladat

Írjunk programot, ami kiszámítja János gazdának a szobák számát, a legnagyobb szoba méretét, és az egyetlen fal kibontásával létrehozható legnagyobb szoba méretét. Adjuk meg továbbá, hogy melyik falat kell kibontani a legnagyobb szoba kialakításához.

Bemenet

  • A bemenet első sorában M és N található (1 <=M,N<=50).
  • Ezután a kastély kódolása következik, N sorban, mindegyikben M egész, a fenti kódolás szerint.

Kimenet

  • első sor: a szobák száma eredetileg
  • a legnagyobb szoba mérete
  • a legnagyobb létrehozható szoba mérete, ha egy falat bonthatunk ki
  • a fal koordinátái, amit kell bontani a legnagyobb szoba kialakításához; ha több fal is megfelel, akkor legnyugatabbra, azon belül legdélebbre kell bontani, és vagy az északi falat, vagy ha az nem jó, akkor a keletit. Kiírandó a mező két koordinátája, majd egy 'N' vagy egy 'E'.

Példa

Bemenet  Kimenet
7 4
11 6 11 6 3 10 6
7 9 6 13 5 15 5
1 10 12 7 13 7 5
13 11 10 8 10 12 13

5
9
16
4 1 E


Tesztadatok

Címkék

A feladat forrása: USACO training material, The Castle
Algoritmusok: 

megoldás