Embedded Files
http://zerojudge.tw/ShowProblem?problemid=d039
內容 ：
尼斯湖水怪是一隻住在尼斯湖中神秘且不明的動物。尼斯湖則是北蘇格蘭的印芬尼斯市附近的一個大且深的淡水湖。尼斯怪通常被視為一種湖怪。
http://en.wikipedia.org/wiki/Loch_Ness_Monster
背景
2003 年 7 月，BBC (英國國家廣播電視公司) 曾報導了一項他們對尼斯湖所作的大規模研究，他們用 600 支聲納也沒有辦法在湖中找到任何「水怪」(也就是任何已知或未知的大型動物) 的踪跡。他們推論尼斯怪並不存在。現在我們要重覆這項實驗。
問題
給你一個 n 列 m 行的格子代表尼斯湖，6 ≤ n, m ≤ 10000，找出最少要放幾個聲納才能控制所有的方格，條件如下：
一個聲納佔一格；它的監控範圍為所在的那一格及緊鄰的格子；
邊緣的格子不需要監控，因為尼斯怪太大了，無法蔵在那兒。
例如，
其中 X 代表聲納，灰色區域則是它所監控的範圍。最後一個圖則是一組可接受的解答。
輸入說明
輸入的第一行有一個整數，t，代表測試筆數。每筆測資一行，含有兩個由空白分開的數字，6 ≤ n, m ≤ 10000，也就是格子的大小 (n 列 m 行)。
輸出說明 ：
每筆測資輸出一行，顯示符合上述條件的最小數字。
範例輸入 ：
若題目沒有特別說明，則應該以多測資的方式讀取，若不知如何讀取請參考 a001 的範例程式。
3
6 6
7 7
9 13
範例輸出 ：
4
4
12
提示 ：
出處 ：
UVa ACM 11044 (管理：snail)
Page updated
Google Sites
Report abuse