d039：11044 - Searching for Nessy (26)

d039: 11044 - Searching for Nessy (26)

更新時間：2016/12/21

內容：
  尼斯湖水怪是一隻住在尼斯湖中神秘且不明的動物。尼斯湖則是北蘇格蘭的印芬尼斯市附近的一個大且深的淡水湖。尼斯怪通常被視為一種湖怪。
背景
  2003 年 7 月，BBC (英國國家廣播電視公司) 曾報導了一項他們對尼斯湖所作的大規模研究，他們用 600 支聲納也沒有辦法在湖中找到任何「水怪」(也就是任何已知或未知的大型動物) 的踪跡。他們推論尼斯怪並不存在。現在我們要重覆這項實驗。
問題
  給你一個 n 列 m 行的格子代表尼斯湖，6 ≤ n, m ≤ 10000，找出最少要放幾個聲納才能控制所有的方格，條件如下：
    一個聲納佔一格；
    它的監控範圍為所在的那一格及緊鄰的格子；
    邊緣的格子不需要監控，因為尼斯怪太大了，無法蔵在那兒。
例如，

其中 X 代表聲納，灰色區域則是它所監控的範圍。最後一個圖則是一組可接受的解答。
輸入說明：
  輸入的第一行有一個整數，t，代表測試筆數。每筆測資一行，含有兩個由空白分開的數字，6 ≤ n, m ≤ 10000，也就是格子的大小 (n 列 m 行)。
輸出說明：
  每筆測資輸出一行，顯示符合上述條件的最小數字。
範例輸入：
  3
  6 6
  7 7
  9 13
範例輸出：
  4
  4
  12
提示：



想一想，再看解答~


我的解題想法：
  因為邊緣的格子不需要監控，所以監控區域的長少2、寬少2。因為輸出要求是最小的數字(使用最少的聲納)，所以每個聲納探測的範圍不會重疊，亦即探測範圍為 3 X 3 的九宮格。我們把長、寬分開計算。
    A.(監控區域的長-2)除以3，如果整除，即為「長邊」放置聲納的數量；如果不整除，則必須+1才為「長邊」放置聲納的數量。
    B.(監控區域的寬-2)除以3，如果整除，即為「寬邊」放置聲納的數量；如果不整除，則必須+1才為「寬邊」放置聲納的數量。
  把 A 乘以 B，即為所求。

程式碼：

#include <stdio.h>
int main(void){
    int t,n,m;
    scanf("%d",&t);
    for(int i=1;i<=t;i++){
        scanf("%d%d",&n,&m);
        n = n-2;
        m = m-2;
        printf("%d\n",(n/3+(n%3+2)/3)*(m/3+(m%3+2)/3));
    }
    return 0;
}

程式碼解析：

#1：	引入標準輸入/輸出串流。
#2：	主程式開始，回傳引數int，沒有參數。
#3：	宣告3個整數(int)變數「t」、「n」、「m」，範圍–2,147,483,648 到 2,147,483,647。
#4：	從標準輸入讀取格式化數據。讀取1個整數(%d)，指定值給「t」。
#5：	迴圈 for 開始。區域變數「i」，從 1 開始到 t 結束 (int i=1;i<=t;i++)。
#6：	從標準輸入讀取格式化數據。讀取2個整數(%d%d)，指定值給「n」、「m」。
#7：	n 減 2 再存回 n。
#8：	m 減 2 再存回 m。
#9：	將格式化數據顯示到標準輸出。輸出1個整數(%d)「(n/3+(n%3+2)/3)*(m/3+(m%3+2)/3)」。 (n%3+2)/3 與 (m%3+2)/3 是計算沒有餘數時加 0；有餘數時加 1。
#10：	迴圈 for 結束。
#11：	主程式回傳整數「0」。
#12：	主程式結束。