問題描述
蘇菲最近迷上製作巧克力,這天她製作了九顆巧克力三顆原味、三顆咖啡口味、三顆草莓口味;每一種口味都有三個形狀{正方形、圓形、三角形}。她想把這九顆巧克力裝進一個漂亮的禮盒來送給她的好朋友,這個禮盒內部是個 3x3 的方陣。蘇菲對於巧克力的擺放位置有特別的偏好,當她指定位置關係後,請你告訴她,滿足指定關係的擺盒方式共有幾種。
舉例來說,如果蘇菲指定了下面三種位置關係(其中「關係 1」意指正方形原味巧克力會在某一列的最左邊,它的右邊是咖啡正方形巧克力,再右邊是草莓圓形巧克力。),那麼能同時滿足這三種位置關係的擺盒方式有六種,如下所示:
型式 1 表示她會指定某一列中三個巧克力的位置關係;型式2 表示她會指定某一列中相鄰兩個巧克力的位置關係,這兩個巧克力可能是靠左的兩顆,也可能是靠右的兩顆;型式3表示她會指定某一列中最左邊和最右邊的巧克力。要注意,蘇菲有時候只會指定巧克力的口味或形狀,不一定會同時指定。
測試資料的第一列為一個正整數值 N (1 <= N <= 10),代表蘇菲指定了幾組位置關係。接著有N 列,每一列的格式如下:
第一個數字 K (2 <= K <= 3)表示該組關係牽涉到幾個巧克力,間隔一個空白之後,有2.K 個字元,分別代表每個巧克力的顏色和形狀,字元間以一個空白隔開。
{除了形式3的中間巧克力為 ? ?,每個巧克力可能同時指定口味及形狀,也可能只指定口味或形狀,但不會兩種皆不指定}
字元代表意義如下表:
巧克力口味 | 巧克力形狀 | ||
字元 | 意義 | 字元 | 意義 |
P | 草莓口味 | S | 正方形 |
B | 原味 | C | 圓形 |
Y | 咖啡口味 | T | 三角形 |
? | 不限口味 | ? | 不限形狀 |
請輸出滿足蘇菲指定關係的擺盒方式共有幾種?
範例一: 3 3 B S Y S P C 3 P T B C Y T 3 P S B T Y C 範例二: 3 3 B S Y ? ? C 2 B C Y T 3 P S ? ? Y C
範例一: 6 範例二: 24