d053：10970 - Big Chocolate (33)

d053: 10970 - Big Chocolate (33)

更新時間：2016/12/22

內容：
  Mohammad 最近去瑞士。因為他很愛他的朋友們，他決定要買巧克力請他們，但是由於這麼高級的巧克力很貴 (你也知道Mohammad 有點小氣！)，他只買得起一片巧克力，很大的一片巧克力 (大到圖 1 也看不到全部) 來請他的朋友們。現在，他要給他的朋友每人一小塊，因為他相信人生而平等，他要每一小塊都一樣大。
  這巧克力是由 M×N 個單位大小的正方形所構成的 M×N 矩形。你也可以假設 Mohammad 剛好有 M×N 個朋友等著吃巧克力。切割巧克力時，Mohammad 可以以垂直或水平的方向沿著小方塊間的溝槽切割。切割開來的每一塊也要分別單獨地以同樣的方式來處理，直到他有 M×N 塊單位大小的巧克力為止。不幸的是，由於他很懶，只要能完成工作，他希望切越少刀越好。
  你的目標就是要告訴他要把這些巧克力方塊全切開至少需要幾刀。

圖1. Mohammad 的巧克力

輸入說明：
  輸入有好幾筆測試資料。輸入的每一行有兩個整數 1≤M≤300 表示巧克力有幾列，1≤N≤300 表示巧克力有幾欄。重覆處理輸入直到檔案結束。

輸出說明：
  針對每行輸入，你的程式要輸出一行，在該行中含有要把整個巧克力切成單位大小方塊所需要的最少刀數。

範例輸入：
  2 2
  1 1
  1 5

範例輸出：
  3
  0
  4

提示：一星秒殺題

想一想，再看解答~

我的解題想法：

  原本思考長邊、短邊哪一個先計算會最少刀數，但仔細分析後，順序並不會影響最後的結果。此題目的刀數，並不像現實中一樣，可以拿多個相同大小的巧克力排列或堆疊後，一刀切下去；或是東西太長，刀子太短，在現實中是無法一刀就切完，但這邊允許這樣的情況為一刀。
  先選一邊切，假設選 m ，那麼全部切開所需的刀數：m - 1
  因為是長方形，所以切完後，每一小塊都是同樣的大小(有 m 塊)，所需的刀數也是一樣的。每一小塊所需的刀數：n - 1
  總刀數：(m - 1) + m*(n - 1) = m*n - 1

程式碼：

#include <stdio.h>
int main(void){
    int m,n;
    while(~scanf("%d%d",&m,&n)){
        printf("%d\n",m*n-1);
    };
    return 0;
}

程式碼解析：

#1：	引入標準輸入/輸出串流。
#2：	主程式開始，回傳引數int，沒有參數。
#3：	宣告2個整數(int)變數「m」、「n」，範圍–2,147,483,648 到 2,147,483,647。
#4：	迴圈 while 開始。使用 while 搭配 scanf 判斷資料是否結束。從標準輸入讀取格式化數據。讀取2個整數(%d%d)，依序指定值給「m」、「n」。
#5：	將格式化數據顯示到標準輸出。輸出1個整數並換行(%d\n)「 m*n - 1 」。
#6：	迴圈 while 結束。
#7：	主程式回傳整數「0」。
#8：	主程式結束。