傳說中,大陸人的幾何學(簡稱大陸幾何學)與平凡的幾何學不同,是門高深且帶有些許神秘色彩的學問。例如,在大陸幾何學中,長方形的其中一個邊長可能會大於另外三邊長的和。
因為大陸幾何學實在是太艱深了,所以這裡只談談大陸幾何學的其中一個應用:大陸方陣。
大陸方陣是一個能夠有效抵禦進攻的軍隊布陣方式,以下將會描述大陸方陣的結構。
假設現在有一塊長方形的空地,首先將這塊空地切成N*M的小方形空地,接著軍隊的每個營安置在小空地中。
安置完畢後,大陸方陣即成形。此時每個小空地可能處於四種狀態:
(1) 裡面沒有軍隊,以符號.
表示。
(2) 裡面有東西向列隊的軍隊,以符號-
表示。
(3) 裡面有南北向列隊的軍隊,以符號|
表示。
(4) 裡面有處於分散狀態的軍隊,以符號+
表示。
我們可以用符號代表一個小空地的狀態,就可以簡單地用俯視圖表達方陣的結構。為了方便,我們以上方代表北方。
為甚麼要這樣標示呢?因為在這樣的標示下,圖上包含幾個矩形,就是這個方陣的「能力指標」!
大陸數學家告訴我們,每種大陸方陣的防禦力強度可以表示為能力指標的函數,但是兩者的關係為何,已經超出凡人的理解範圍。
所以現在給你一個大陸方陣,請你求出它的能力指標。剩下的事情交給大陸數學家就可以了。
能力指標的完整定義方式如下:
能力指標的數值,代表在大陸方陣中,能找到幾個端點位置不完全相同的矩形部分$Q$,使得:
(1) $Q$只包含完整的小空地。
(2) $Q$的每個邊長至少是2倍小空地的邊長。
(3) $Q$的最南端與最北端兩排的小空地都需要有軍隊,且其為東西向列隊或處於分散狀態。
(4) $Q$的最東端與最西端兩排的小空地都需要有軍隊,且其為南北向列隊或處於分散狀態。
(5) $Q$四個角落的小空地都需要有處於分散狀態的軍隊。
例如,以下幾個都是滿足上述五個條件的矩形:
+---+ +---+ |
+---+ +...| +-+-+ |
++-+ |-+| +-++ |
++ ++ |
以下幾個則不是:
++++ | +-|-+ +.+.- +---+ |
---| |..| |--+ |
++ -+ |
第一行有兩個數字$N,M$,分別代表大陸方陣的長和寬。(保證$N\leq M\leq 1200$)
接下來有$N$行,每行有$M$個字元,描述大陸方陣的長相。
子任務(測資) | 額外限制 | 分數 |
1 (0~3) | $N,M\leq 50$ | 4 |
2 (0~7) | $N,M\leq 120$ | 16 |
3 (0~10) | $N,M\leq 700$ | 17 |
3 (11~13) | $N\leq 10$ | 19 |
5 (0~17) | 無限制 | 44 |
輸出一個數字,代表給定大陸方陣的能力指標。
+-+-+--+
|..+|-++
----++++
++..+..|
++-----+
Problem Set by Yihda Yol
Problem Source: TOI 2017 二階練習題
No. | Testdata Range | Score |
---|---|---|
1 | 0~3 | 4 |
2 | 0~7 | 16 |
3 | 0~10 | 17 |
4 | 11~13 | 19 |
5 | 0~17 | 44 |