ДАРХАНЫ 26-р ДУНД СУРГУУЛЬ / USACO /

Цайз доорхи хэлбэртэй.

     1   2   3   4   5   6   7

   #############################

 1 #   |    #    |    #    |    |     #

   #####---#####-----#-----#####-----#  

 2 #    #   |    #    #    #    #    #

   #-----#####-----#####-----#####-----#

 3 #    |    |    #    #    #    #   #  

   #-----#########-----#####------#----#

 4 # -> #    |    |     |    |     #   #  

   #############################

Зурганд

   # хана

   - хана биш

   | хана биш

   ->нураавал зохих ханыг заасан заагч

Зурагт нэгэн цайзын зураг өгөгджээ. Тэгвэл доорх асуултуудад хариулах програм бич.

  А. Цайз хэдэн өрөөтэй вэ?

  Б. Хамгийн том өрөөний талбай.

  С. Аль ханыг нурааж хоёр өрөөг нийлүүлбэл хамгийн их талбайтай өрөө үүсэх вэ?

Цайзыг N*M ширхэг дэд модулиудад хуваасан. Үүнд модуль бүр нь хоорондоо тэгээс дөрвөн ханатай болно (N,M<=50)

Оролт

Модуль бүр нэг тоогоор тодорхойлогдоно.

Эхний мөрөнд цайзын өргөн болох N тоо

2 дахь мөрөнд цайзын урт болох М тоо

Түүний дараагийн N мөрөнд М ширхэг тоо байх ба тоо бүр нэг модулийн тухай мэдээллийг агуулна. Үүнд : Модулийн тухай мэдээлэл гэдэг нь уг модулийг тойрсон ханануудын тухай мэдээлэл ба ханануудыг доорхи байдлаар дүрсэлсэн.

1  баруун талдаа ханатай

2  хойд талдаа ханатай

4  зүүн талдаа ханатай

8  өмнө талдаа ханатай

Энд хана бүр нь хоёр удаа тодорхойлогдож байгаа . Жишээ нь: 1,1  

модулийн өмнөд хана 2,1 модулийн хойд хана болно. Ямарваа нэг модулийн хананы тухай мэдээлэл нь эдгээр хана тус бүрийн мэдээллүүдийн нийлбэр байдлаар өгөгдөнө. Цайз ядаж 2 өрөөтэй .

Гаралт

1-р мөрөнд цайз дахь өрөөний тоо

2-р мөрөнд цайз дахь хамгийн том талбайтай өрөөний талбай

3-р мөрөнд ямар ханыг нураавал хамгийн том талбайтай өрөө үүсч болох ханын координат, мөн тухайн ханыг нураахдаа зөвхөн баруунаас зүүн тийш, эсвэл хойноос урагш чиглэлд нураахаар өрөөг сонгоно. Зүүн талын ханыг нураах бол E, урд талын ханыг нураах бол N үсгийг хэвлэнэ.   

Жишээ

Оролт : /Дээр өгөгдсөн зургийн хувьд оролт нь дараах байдалтай байна./

4

7

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

Орчуулсан : Л.Баярхүү