2314 . 拆譜問題
TopCoder
Tags
Description
PCC 在玩節奏遊戲，然後發現他怎樣也打不過千本櫻。於是，他決定聽從同學的意見，去網路上找千本櫻的的譜面來觀察。
一個譜面可以表示成一個 $n \times m$ 矩陣，每個格子都是 '$*$'、'$-$' 其中一個。其中，一個按鍵為一列中，連續兩個以上的 '$-$'。遊戲開始時，PCC 可以將任意數量的手指放在最上面的橫排的任何位置，並且每一秒每一隻手指可以分別往左或往右移動一格，也可以不移動（不可以移出矩陣外，且手指不可重疊）。每一秒譜面會往上移動一排。
當某一列移動到跟手指同列時我們稱該列擊打成功若 :
1）該列沒有任何按鍵
2）對於所有的按鍵，都至少有一隻手指按到
其中一個成立。
我們稱 full combo 若 $n$ 列全部都擊打成功。
另外，這個譜面有一些很特別的條件：
- 對於每一列，每一個 '$-$' 至少有一個相鄰的 '$-$'
- 對於每一列，按鍵數量不多於兩個
- 保證在 $n\times m$ 個格子裡至少有一個是 '$-$'
請問至少需要多少隻手指才可以 full combo 這個譜面？
Input Format
第一行輸入 $T$，表示測資數
對於每筆測資：第一行輸入 $n,m$，接下來 $n$ 行輸入長度為 $m$ 的字串（由 '$*$'、'$-$' 組成）
對於所有測試資料：
- $1\le T \le 100$
- $1\le n \le 2 \times 10 ^ 5,\sum n \le 5 \times 10 ^ 5$
- $2 \le m \le 8$
- 對於每一列，每一個 '$-$' 至少有一個相鄰的 '$-$'
- 對於每一列，按鍵數量不多於兩個
- 保證在 $n\times m$ 個格子裡至少有一個是 '$-$'
Output Format
輸出 $T$ 行，每行為一個整數，表示最少需要幾隻手指。
Sample Input 1
1
5 5
***--
--***
**--*
*----
--*--
5 5
***--
--***
**--*
*----
--*--
Sample Output 1
2
Hints
對於範例測資，可以證明這張譜至少需要兩隻手指。
其中一種可能性為 $($第一隻手指$,$第二隻手指$)$：$(2,4)\to (1,3)\to (2,3)\to (2,3)\to (2,4)$
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0 | 範例測資 | 0 |
| 2 | 0~5 | $n\le 15$ | 23 |
| 3 | 6~10, 15, 18 | $m\le 4$ | 11 |
| 4 | 0, 5~20, 32 | $m \le 6$ | 13 |
| 5 | 0~32 | 無其他限制 | 53 |