22 地盘划分

22 地盘划分

修罗王和邪狼被关进监狱，该监狱的地下秩序实际被不少暗势力所把持，这些暗势力根据其实力不同，划分出了大大小小的势力范围。具体划分方式是这样的：监狱是一个给定的矩形，每一个暗势力的势力范围都必须是一个正方形，划分时，最大的暗势力尽可能多地从矩形中划分一块正方形，接下来，第二大的暗势力在剩下的矩形中尽可能多的划分一块正方形……例如，图2.1中所示是一个3×4的矩阵，可最少划分为４个势力范围。

也就是说，取走一个3×3的正方形后，将问题规模变成3×1，然后变成2×1，最后变成1×1。规模每缩小一次，正方形的个数加1。

image.png

【输入格式】

输入文件为territory.in，两个int整数，即长和宽。

【输出格式】

输出文件为territory.out，即正方形最少个数。

【输入样例】

３　4

【输出样例】

４

package algorithmclassic.ch02;

import java.util.Scanner;

/**
 * @author Dylan
 * @date 2020/5/5 - 10:19
 */
public class Q22 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        if(n < m){
            int temp = n;
            n = m;
            m = temp;
        }
        int cnt = f(n, m);
        System.out.println(cnt);
    }

    public static int f(int n, int m){
        if(n <= m) return 1;
        int nn = n;
        n = m;
        m = nn - m;
        if(n < m){
            int temp = n;
            n = m;
            m = temp;
        }
        return 1 + f(n,m);
    }
}