d053 UVa 10970 - Big Chocolate

出處 http://zerojudge.tw/ShowProblem?problemid=d053

內容 ：

Mohammad 最近去瑞士。因為他很愛他的朋友們，他決定要買巧克力請他們，但是由於這麼高級的巧克力很貴 (你也知道Mohammad 有點小氣！)，他只買得起一片巧克力，很大的一片巧克力 (大到圖 1 也看不到全部) 來請他的朋友們。現在，他要給他的朋友每人一小塊，因為他相信人生而平等，他要每一小塊都一樣大。

這巧克力是由 M×N 個單位大小的正方形所構成的 M×N 矩形。你也可以假設 Mohammad 剛好有 M×N 個朋友等著吃巧克力。

切割巧克力時，Mohammad 可以以垂直或水平的方向沿著小方塊間的溝槽切割。切割開來的每一塊也要分別單獨地以同樣的方式來處理，直到他有 M×N 塊單位大小的巧克力為止。不幸的是，由於他很懶，只要能完成工作，他希望切越少刀越好。

你的目標就是要告訴他要把這些巧克力方塊全切開至少需要幾刀。

輸入說明 ：

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

輸出說明 ：

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

範例輸入 ：

2 2

1 1

1 5

範例輸出 ：

3

0

4

提示 ：

一星秒殺題

出處 ：

UVa ACM 10970 (管理：snail)

解題策略

注意 2x2 巧克力要用3刀，一刀切開後分成兩部分，每一部分需分別再用一刀切開，總共三刀。

待完成程式