TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

50.0% (1/2)

Submission's AC Ratio

30.0% (3/10)

Tags

Description

傳說中,大陸人的幾何學(簡稱大陸幾何學)與平凡的幾何學不同,是門高深且帶有些許神秘色彩的學問。例如,在大陸幾何學中,長方形的其中一個邊長可能會大於另外三邊長的和。

因為大陸幾何學實在是太艱深了,所以這裡只談談大陸幾何學的其中一個應用:大陸方陣。
大陸方陣是一個能夠有效抵禦進攻的軍隊布陣方式,以下將會描述大陸方陣的結構。

假設現在有一塊長方形的空地,首先將這塊空地切成N*M的小方形空地,接著軍隊的每個營安置在小空地中。
安置完畢後,大陸方陣即成形。此時每個小空地可能處於四種狀態:
(1) 裡面沒有軍隊,以符號.表示。
(2) 裡面有東西向列隊的軍隊,以符號-表示。
(3) 裡面有南北向列隊的軍隊,以符號|表示。
(4) 裡面有處於分散狀態的軍隊,以符號+表示。
我們可以用符號代表一個小空地的狀態,就可以簡單地用俯視圖表達方陣的結構。為了方便,我們以上方代表北方。

為甚麼要這樣標示呢?因為在這樣的標示下,圖上包含幾個矩形,就是這個方陣的「能力指標」!
大陸數學家告訴我們,每種大陸方陣的防禦力強度可以表示為能力指標的函數,但是兩者的關係為何,已經超出凡人的理解範圍。
所以現在給你一個大陸方陣,請你求出它的能力指標。剩下的事情交給大陸數學家就可以了。


能力指標的完整定義方式如下:
能力指標的數值,代表在大陸方陣中,能找到幾個端點位置不完全相同的矩形部分$Q$,使得:
(1) $Q$只包含完整的小空地。
(2) $Q$的每個邊長至少是2倍小空地的邊長。
(3) $Q$的最南端與最北端兩排的小空地都需要有軍隊,且其為東西向列隊或處於分散狀態。
(4) $Q$的最東端與最西端兩排的小空地都需要有軍隊,且其為南北向列隊或處於分散狀態。
(5) $Q$四個角落的小空地都需要有處於分散狀態的軍隊。

例如,以下幾個都是滿足上述五個條件的矩形:

+---+
+---+
+---+
+...|
+-+-+
++-+
|-+|
+-++
++
++

以下幾個則不是:

++++ +-|-+
+.+.-
+---+
---|
|..|
|--+
++
-+

Input Format

第一行有兩個數字$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

Output Format

輸出一個數字,代表給定大陸方陣的能力指標。

Sample Input

5 8
+-+-+--+
|..+|-++
----++++
++..+..|
++-----+

Sample Output

3

Hints

+-+-+--+
|..+|-++
----++++
++..+..|
++-----+

Problem Source

Problem Set by Yihda Yol
Problem Source: TOI 2017 二階練習題

Subtasks

No. Testdata Range Score
1 0~3 4
2 0~7 16
3 0~10 17
4 11~13 19
5 0~17 44

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 900 65536 262144 1 2 3 5
1 900 65536 262144 1 2 3 5
2 900 65536 262144 1 2 3 5
3 900 65536 262144 1 2 3 5
4 900 65536 262144 2 3 5
5 900 65536 262144 2 3 5
6 900 65536 262144 2 3 5
7 900 65536 262144 2 3 5
8 1800 65536 262144 3 5
9 1800 65536 262144 3 5
10 1800 65536 262144 3 5
11 900 65536 262144 4 5
12 900 65536 262144 4 5
13 900 65536 262144 4 5
14 2500 65536 262144 5
15 2500 65536 262144 5
16 2500 65536 262144 5
17 2500 65536 262144 5