TopCoder

User's AC Ratio

NaN% (0/0)

Submission's AC Ratio

NaN% (0/0)

Tags

Description

傳說中的尋寶公會 YTPirates,由神祕的主辦人 YTP 一手創立,名震江湖數十年。公會內部的最高職位稱作 whi-TP,據說公會上下每個成員都酷愛刷牙,個個一口白牙閃閃發亮,因此外人都稱他們是 whi-TPirates(White Teeth Pirates),久而久之這個稱號也成了掌權者的正式頭銜。

如今 YTP 年事已高,即將退隱,決定舉辦一場尋寶大賽,選出唯一的繼承人。比賽使用一張 $R \times C$ 的長條島鏈圖,每個格子皆為陸地或海洋,地圖將直接給定。凡是能在這張地圖上畫出最多藏寶記號者,便能成為下一任 whi-TP,繼承那份代代相傳、只有掌權者才看得懂的祕密繪圖術。

船長 owoovo 人稱江湖刷牙第一人,傳說他連挖寶藏都是用牙刷,也有人說他把整片海洋當成自己的開心水族箱。江湖上都說,若 owoovo 真能奪下 whi-TP 之位,YTPirates 恐怕就要改名叫「owoovo 刷牙幫」了。

owoovo 之所以能稱霸尋寶界,除了他無與倫比的刷牙技術之外,更重要的是他那把全世界最長的鬍子——長到可以像藤蔓一樣盪來盪去。他習慣用自己的鬍子在地圖上畫出藏寶記號,每個記號固定佔一個 $3 \times 3$ 的範圍,其中四個角落格與正中央格(共五格)連起來剛好形成一個大大的 X。這五格是鬍子甩動時真正接觸地面、埋著寶藏的寶藏本體;其餘上下左右四個邊格,則只是鬍子在半空中揮過、單純經過的鬍子軌跡

為了方便描述,若以 O 標記寶藏本體、以 x 標記鬍子軌跡,一個記號長這樣:

OxO
xOx
OxO

畫記號時規則如下:

  • 記號必須完整落在地圖範圍內;
  • 寶藏本體的五個格子都必須位於陸地上,且任兩個記號的寶藏本體不能共用任何一格
  • 鬍子軌跡完全沒有限制:可以落在陸地或海洋,也可以和任何其他記號的寶藏本體或鬍子軌跡重疊。

前資奧國手 guagua0407 曾說過一句名言:「如果在森林裡同時遇到 owoovo 和一個普通男人,我會毫不猶豫選擇 owoovo。」——他是 owoovo 的頭號粉絲。然而,這次繼承人之位只有一人能夠獲得,guagua0407 也想放手一搏。他報名了 YTPirates 主辦的這場比賽,想跟 owoovo 一較高下,也想親眼見證傳說。

guagua0407 原本想自己研究這張地圖,先找出最多能畫出多少個藏寶記號,這樣在挑戰 owoovo 時也能更有底氣。但此時的他正忙著跑到森林裡向 owoovo 下戰帖,只好把這個問題交給你,請你幫忙算出在這張地圖上最多能畫出的藏寶記號數量。

Input Format

第一行有兩個以空白隔開的整數 $R, C$,代表地圖的列數與行數。

接下來有 $R$ 行,每行是一個長度為 $C$ 的字串,只由 .# 組成,描述整張地圖:

  • . 代表該格是陸地
  • # 代表該格是海洋

其中,由上往下數的第 $i$ 個字串的第 $j$ 個字元,代表第 $i$ 列第 $j$ 行的格子($1 \leq i \leq R$,$1 \leq j \leq C$)。

  • $3 \leq R \leq 12$
  • $3 \leq C \leq 10^ 5$
  • 地圖的每個格子都是 .(陸地)或 #(海洋)

Output Format

輸出一行一個整數,代表在這張地圖上最多能畫出的記號數量。

注意:一個記號都畫不出來時,請輸出 $0$。

Sample Input 1

3 6
......
....#.
......

Sample Output 1

2

Sample Input 2

6 4
....
....
....
....
....
....

Sample Output 2

4

Hints

範測 1 解釋:

AB 為兩個記號的寶藏本體,. 為沒被用到的陸地,# 為海洋:

ABAB..
.AB.#.
ABAB..

記號的左上角只能落在第 $1$ 列的第 $1 \sim 4$ 行,其中第 $4$ 行會讓正中央格落在海洋上;剩下的三個位置無法同時取三個,因此答案為 $2$。

範測 2 解釋:

整張地圖都是陸地,上下兩半各放兩個記號、互不干擾,因此答案為 $4$:

ABAB
.AB.
ABAB
CDCD
.CD.
CDCD

Problem Source

2026 YTP 高中組決賽 p13

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測試資料 0
2 2~10 $R = 3$ 3
3 0~1, 11~25 $C \leq 100$ 7
4 26~42 $R$ 是偶數 10
5 0~48 無額外限制 5

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 2000 262144 65536 1 3 5
1 2000 262144 65536 1 3 5
2 2000 262144 65536 2 5
3 2000 262144 65536 2 5
4 2000 262144 65536 2 5
5 2000 262144 65536 2 5
6 2000 262144 65536 2 5
7 2000 262144 65536 2 5
8 2000 262144 65536 2 5
9 2000 262144 65536 2 5
10 2000 262144 65536 2 5
11 2000 262144 65536 3 5
12 2000 262144 65536 3 5
13 2000 262144 65536 3 5
14 2000 262144 65536 3 5
15 2000 262144 65536 3 5
16 2000 262144 65536 3 5
17 2000 262144 65536 3 5
18 2000 262144 65536 3 5
19 2000 262144 65536 3 5
20 2000 262144 65536 3 5
21 2000 262144 65536 3 5
22 2000 262144 65536 3 5
23 2000 262144 65536 3 5
24 2000 262144 65536 3 5
25 2000 262144 65536 3 5
26 2000 262144 65536 4 5
27 2000 262144 65536 4 5
28 2000 262144 65536 4 5
29 2000 262144 65536 4 5
30 2000 262144 65536 4 5
31 2000 262144 65536 4 5
32 2000 262144 65536 4 5
33 2000 262144 65536 4 5
34 2000 262144 65536 4 5
35 2000 262144 65536 4 5
36 2000 262144 65536 4 5
37 2000 262144 65536 4 5
38 2000 262144 65536 4 5
39 2000 262144 65536 4 5
40 2000 262144 65536 4 5
41 2000 262144 65536 4 5
42 2000 262144 65536 4 5
43 2000 262144 65536 5
44 2000 262144 65536 5
45 2000 262144 65536 5
46 2000 262144 65536 5
47 2000 262144 65536 5
48 2000 262144 65536 5