TopCoder

User's AC Ratio

58.5% (24/41)

Submission's AC Ratio

15.4% (38/247)

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
***--
--***
**--*
*----
--*--

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

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 2000 65536 65536 1 2 4 5
1 2000 65536 65536 2 5
2 2000 65536 65536 2 5
3 2000 65536 65536 2 5
4 2000 65536 65536 2 5
5 2000 65536 65536 2 4 5
6 2000 65536 65536 3 4 5
7 2000 65536 65536 3 4 5
8 2000 65536 65536 3 4 5
9 2000 65536 65536 3 4 5
10 2000 65536 65536 3 4 5
11 2000 65536 65536 4 5
12 2000 65536 65536 4 5
13 2000 65536 65536 4 5
14 2000 65536 65536 4 5
15 2000 65536 65536 3 4 5
16 2000 65536 65536 4 5
17 2000 65536 65536 4 5
18 2000 65536 65536 3 4 5
19 2000 65536 65536 4 5
20 2000 65536 65536 4 5
21 2000 65536 65536 5
22 2000 65536 65536 5
23 2000 65536 65536 5
24 2000 65536 65536 5
25 2000 65536 65536 5
26 2000 65536 65536 5
27 2000 65536 65536 5
28 2000 65536 65536 5
29 2000 65536 65536 5
30 2000 65536 65536 5
31 2000 65536 65536 5
32 2000 65536 65536 4 5