回分類題庫
h147: B.盜墓迷城
關鍵字: NPSC 2015 高中組初賽

測資點 : 4 | Time Limit : 10000 ms | Memory Limit : 128000 KB
Accepted : 36 Times / 19 Users | Submit : 217 Times / 30 Users | Accepted rate : 63%
題目加入時間 : 2016-09-07 15:55

Content: 简体中文

數百年前有一位盜墓專家艾迪,闖遍了各地大大小小的陵墓。

其實,早在秦始皇陵墓被挖掘出土前的幾百年,他就已經早先一步得知了陵墓的位置並闖了進去。陵墓內部暗道重重,地道峰迴路轉,暗房機關四佈。

艾迪在迷宮裡打轉了許久,好不容易在牆上發現了一處暗門。一推開,裡頭竟擺滿了大大小小的兵馬俑。仔細一看,它們排成了 N 列 M 行的矩形,其中大致上可分為步兵俑、弩兵俑以及騎兵俑。身為收藏狂的艾迪當然希望能把面前的兵馬俑都帶回去收藏,但此時他想起了他的祖傳盜墓守則,記載著以下的事情:取走的兵馬俑原先一定要排成一個矩形,而且其中的步兵俑和騎兵俑數量要一樣,若違反了這條規則,整座陵墓就會因此陷落。

雖然艾迪很想要收藏這些文物,但如果陵墓坍塌了他就會葬身於此。所以,艾迪想請你告訴他,在能安全脫身的情況下他最多能帶走幾座兵馬俑。

舉例來說(第二筆範例),下圖是一個 N = 3, M = 4 的兵馬俑陣,其中 A 代表步兵,B 代表弩兵,C 代表騎兵。而圖中綠色矩形是一種可行的取法,可以帶走 4 尊兵馬俑,但不是最多的。圖中藍色或是黃色的取法皆可以帶走 6 尊兵馬俑,也是所有可行方法中最多的。因此艾迪最多能帶走 6 座兵馬俑。 

 

Input:

輸入的第一行有一個整數 T,代表共有幾筆測試資料。 

每筆測試資料的第一行包含兩個正整數 N, M,以單一空白字元隔開,代表兵馬俑排列成 N 列 M 行。

接下來共有 N 行,其中每一行有一個長度 M 的字串 Si,表示第 i 列中的兵馬俑依序是哪一種類型,其中 'A' 代表步兵,'B' 代表弩兵,'C' 代表騎兵。

Output:

對於每筆測試資料請輸出一行,恰包含一個整數,表示艾迪最多能夠帶走的兵馬俑數量。

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
2
3 4
AACA
AAAA
AAAA
3 4
ABBC
ABBA
CBBA

Sample Output :

2
6

Hint :

Author :

NPSC 2015 高中組初賽 (管理員:sagit)

  Solve it!   Status Forum