Problem : 311 - The Castle

Problem Statistics

Solved Member: 16　　Submission: 33　　User Tried: 17

Statement:

考慮一座由 # , | 及 - 所組成的城堡：

# = 牆壁 , -及| = 沒有牆壁
-> = 使得新房間的面積最大所需要移除的牆壁

範例中，此座城堡被分成 7 x 4 個區塊。一間「房間」代表著由連續區塊(即沒有被#所分隔)組成的一個空間，此座城堡有五個房間(面積為 9 , 7 , 3 , 1 和 8)。

把箭頭指向的牆壁移除掉，會得到一個最大可能面積的房間。

測試資料中，保證每座城堡至少兩個房間且一定有能夠被移除的牆壁。

Input:Output:

地圖以數字的方式表示，一個數字代表一個區塊，城堡以N行以及每行M個數字表示。

每個區塊周圍所擁有的牆壁用以下方法表示：

1: 西側牆壁
2: 北側牆壁
4: 東側牆壁
8: 南側牆壁

假設一個區塊擁有西邊及北邊的牆壁，則這個區塊應以3(1+2)來表示。

第一行有兩個數字 M,N 分別代表長與寬。 ( 1 <= M , N <= 50 )

接下來有N行(依序從北到南)，每行有M個數字代表這個區塊周圍的牆壁分佈。

請輸出四行：

第一行：此座城堡有幾個房間
第二行：最大房間的面積
第三行：移除一面牆壁所形成最大可能房間的面積
第四行：哪一面牆壁

第四行牆壁的格式為： x y N或E ，分別代表所屬區塊為第幾列、第幾行、北邊(N)的牆壁或是東邊(E)的牆壁

假使有多組答案，則依

順位一：所屬區塊最靠西邊
順位二：所屬區塊最靠南邊
順位三：區塊的北側牆壁優先

輸出一組答案

Sample Input:Sample Output:

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

Source:

IOI 1994

Problem Setter

andrew704

Testdata:

Test	Time	Memory	Score
0	1000ms	65536kb
1	1000ms	65536kb	14
2	1000ms	65536kb	14
3	1000ms	65536kb	14
4	1000ms	65536kb	14
5	1000ms	65536kb	14
6	1000ms	65536kb	15
7	1000ms	65536kb	15