2011年8月29日 星期一

11553 - Grid Game


愛莉絲與鮑伯兩人有很多糖果,他們以糖果為賭注來玩遊戲。首先,他們以隨機選擇的數字填滿 n x n 的表格,愛莉斯劃掉第 i 列後,輪到鮑伯劃掉第 j 行,這一輪結束後,愛莉斯可以從鮑伯那裡拿走表格中第 i 列第 j 行數字的糖果數量,以M(i, j)表示愛莉斯所贏得的糖果數量,若該數為負數,表示愛莉斯要拿出 |M(i, j)| 個糖果給鮑伯。遊戲每一輪都以愛莉斯開始,以鮑伯結束,愛莉斯一定是劃橫列,而鮑伯一定是劃直行,且同一列或行皆不能被重複劃掉。遊戲進行直到所有行列皆被劃掉。本題請問愛莉斯可從鮑伯那裡贏得最多多少顆糖果(或最少輸掉多少顆糖果),假設兩人都做到最佳的劃法。

示意圖
Program Input
輸入的第一列有一個整數 t (1 <= t <= 20)表示測試資料的組數。每組資料一開始給定整數 n (1 <= n <= 8)表示表格的大小,接下來的 n 列每列有 n 個以空白字元隔開整數,第 i 列第 j 行的數值以M(i, j)表示(-1000 <= M(i, j) <= 1000)。

Program Output
請依題意輸出每組測試資料的答案。

INPUT
3
2
10 10
-5 -5
2
10 -5
10 -5
2
10 -5
-5 10
OUTPUT
5
5
-10

原文出處

沒有留言:

張貼留言