10053. Row-Column Game

I'm a slow walker, but I never walk backwards.

題目描述

Morris 和他腦中的小伙伴玩遊戲,遊戲在一個 $n \times n$ 的盤面中進行,每一格分別有一個數字。

規則說明

  1. 玩家輪流從棋盤中取數字
  2. 先手只取水平行,後手只取垂直列
  3. 遊戲剛開始,先手必須從第一行開始取數
  4. 假設先手取 $(i, x)$ 這一格數字,後手必須在 $x$ 列中挑一個數字 ($A(?, x)$)。同樣地,後手若取 $(y, x)$,則先手必須在 $y$ 行中挑一個數字 ($A(y, ?)$)。
  5. 被挑過的數字將不能再次被挑選
  6. 取得數字總和較多者宣告獲勝

現在請你統計所有玩家挑選的可能,回報先手獲勝、後手獲勝、平手情況的最終盤面個數。

輸入格式

每組測資的第一行會有一個 $n$,接下來會有 $n$ 行,每一行上會有 $n$ 個整數,第 $i$ 行上第 $j$ 個整數表示盤面 $A(i, j)$ 上的數字。

  • $1 \le n \le 4$

範例輸入

3
1 2 3
4 5 6
7 8 9
3
1 1 1
1 1 1
1 1 1
4
1 6 9 5
4 6 5 8
2 3 5 7
9 8 6 7

範例輸出

48 24 0
48 0 24
8222 8222 188

範例解說

1 2 3
4 5 6
7 8 9

先手只能在 1, 2, 3 三個挑一個,倘若選 2,則

1   3
4 5 6
7 8 9

後手只能在 5, 8 兩個中挑一個,倘若選 8,則

1   3
4 5 6
7   9

先手只能在 7, 9 中挑一個,倘若選 9,則

1   3
4 5 6
7

後手只能在 3, 6 中挑一個,倘若選 3,則

1  
4 5 6
7

由於只有一個整數,先手只能選 1,則

4 5 6
7

現在後手有 4, 7 可以選,若後手選擇 7,則

4 5 6

先手沒得選,進入中盤計分。先手得分 $12 = 2+9+1$,後手得分 $18 = 8 + 3 + 7$,宣告後手獲勝。

Discussion