算法题4.妞妞的问题

题目描述:

妞妞公主新得到一块白色棋盘。这块棋盘共有n行m列，任意相邻的两个格子都是不同的颜色（黑或白），坐标位（1,1）的格子是白色的。
这一天牛牛来看妞妞公主时，牛牛公主正望着棋盘发呆。牛牛看妞妞公主闷闷不乐的样子，便对妞妞公主说：“只要你告诉我n和m，我能马上算出黑色方块的白色方块的数量。”“这太简单了。”妞妞公主想了一会，“我会在这n行m列中选择一个左下角坐标位（x0，y0）。右上角坐标为（x1，y1）的矩形，把这个矩形里的共（x1-x0+1）*（y1-y0+1）个方块全部涂白。你还能马上算出黑色方块和白色方块的数量吗？”“这太简单了。”牛牛自信一笑，“你还可以在执行涂白操作后再选择一个左下角坐标为（x2，y2），右上角坐标为（x3，y3）的矩形，把这个矩形里的方块全部涂黑。我依然能马上算出黑色方块和白色方块的数量。”
妞妞公主终于惊讶地睁大了眼睛，于是抛出了她的T次提问。
聪明的牛牛当然会做了，但是他想把这个问题交给你，请帮牛牛算出每次提问棋盘的黑白方块数目吧。

输入描述
第一行一个整数T,表示妞妞公主一共提问了T次。
接下来3T行，
第（1+3i）行两个整数n，m。表示第i次提问时棋盘的大小；
第（2+3i）行四个整数x0,x1,y0,y1。表示第i次提问时涂白操作选取的两个坐标。
第（3+3i）行四个整数x2,y2,x3,y3。表示第i次提问时涂黑操作选取的两个坐标。
1<=T<=10000，1<=x<=n<=1000000000，1<=y<=m<=1000000000，x0<=x1，y0<=y1，x2<=x3，y2<=y3。
输出描述
共T行，每行两个整数分别表示白色方块的数量和黑色方块的数量。

输入样例：

3
1 3
1 1 1 3
1 1 1 3
3 3
1 1 2 3
2 1 3 3
3 4
2 1 2 4
1 2 3 3

输出样例

0 3
3 6
4 8

解题思路

格子个数是可以快速维护的，总共分为3步，涉及到3个核心要点。

1. 将(x0,y0),(x1,y1)矩形内的方块都涂白。
2. 将(x2,y2),(x3,y3)矩形内的方块都涂黑
3. 第三步，找到两个矩形的公共部分（该部分中在第一步将所有方块涂白了,而第二步计算时依然按照没涂白之前的计算，也就是少算了第一步之前的黑方块个数），所以需要计算回去。

3个核心要点

• 一个矩形区域内格子总个数为奇数时，白色块比黑色多一个（起始位置时白块，若起始位置为黑块则黑块比白块多一个）；为偶数时，黑白块一样多。
  若区域内起始位置为黑色块，则黑块个数 = (n * m +1 ) /2，白块个数 = n * m /2;反之就反过来计算。
• 若(x，y)坐标位置和为奇数，则该位置是黑方块，否则为白方块。
• 重合区域矩形的计算（详见代码）

参考代码

public class Main {

    /**
     * 格子个数可以快速维护，然后对应维护出来即可
     * 核心要点：
     * 1. 一个矩形区域内格子总个数为奇数时，白色块比黑色多一个；为偶数时，黑白一样多。
     * 2. 若区域内起始位置为黑色块，则黑块个数 = (n * m +1 ) /2，白块个数 = n * m /2;反之就反过来计算
     * 3. 若(x，y)坐标位置和为奇数，则该位置是黑方块，否则为白方块。
     * 4. 重合区域矩形的计算
     */
     public static void main(String[] args) {

        long[] x = new long[4];  //x[i]
        long[] y = new long[4];  //y[i]

        //提问次数
        int T;
        //n行m列   黑色，白色块个数  辅助位
        long n, m, black, white, a, b, c, d, e;
        Scanner scanner = new Scanner(System.in);

        T = scanner.nextInt();
        for (int i = 0; i < T; i++) {
            n = scanner.nextInt();
            m = scanner.nextInt();

            //总个数为奇数时，白色块比黑色多一个；为偶数时，一样多
            black = n * m / 2;
            white = n * m - black;

            //输入(x0,y0) 至 (x3,y3)
            for (int j = 0; j < 4; j++) {
                x[j] = scanner.nextInt();
                y[j] = scanner.nextInt();
            }

            //第一步将(x0,y0),(x1,y1)矩形内的方块都涂白，也就是计算出该区域内 黑方块的个数d，
            //将白方块个数+d,黑方块-d
            //（& 按位与，其实这里跟与2求余效果(% 2)一样，也就是判断是奇数还是偶数）
            if (((x[0] + y[0]) & 1) != 0) {  //d为区域内黑方块的个数
                // 起始位置是黑方块
                d = ((x[1] - x[0] + 1) * (y[1] - y[0] + 1) + 1) / 2;
            } else {
                //起始位置是白方块
                d = (x[1] - x[0] + 1) * (y[1] - y[0] + 1) / 2;
            }
            white += d;
            black -= d;

            //第二步将(x2,y2),(x3,y3)矩形内的方块都涂黑，也就是计算出 白方块的个数d，
            //将白方块个数-d,黑方块+d
            //注意这里的d 是需要涂黑的白方块的个数
            if (((x[2] + y[2]) & 1) != 0) { //d为区域内白方块的个数
                //起始位置是黑方块
                d = (x[3] - x[2] + 1) * (y[3] - y[2] + 1) / 2;
            } else {
                //起始位置是白方块
                d = ((x[3] - x[2] + 1) * (y[3] - y[2] + 1) + 1) / 2;
            }
            white -= d;
            black += d;

            //第三步，找到两个矩形的公共部分，该部分中在第一步将所有方块涂白了，
            // 而第二步计算依然按照没涂白之前的计算，也就是少算了第一步之前的黑方块个数
            //也就是第一步多计算的白方块e，
            //最后白方块个数-e，黑方块个数+e
            a = max(x[0], x[2]);  //重叠部分左上角x
            b = max(y[0], y[2]);  //重叠部分左上角y
            c = min(x[1], x[3]);  //重叠部分右下角x
            d = min(y[1], y[3]);  //重叠部分右下角y

            //e为第一步中被涂白了的黑方块个数，
            // 但在第二步中仍把他当做黑方块涂白了，所以要加回去。
            if (c < a || d < b) {  //没有公共部分 
                e = 0;
            } else {
                if (((a + b) & 1) != 0) {  //e为区域内黑方块的个数
                    // 则起始位置是黑方块
                    e = ((c - a + 1) * (d - b + 1) + 1) / 2;
                } else {
                    //起始位置是白方块
                    e = (c - a + 1) * (d - b + 1) / 2;
                }
            }
            white -= e;
            black += e;

            //%d 输出10进制数
            System.out.printf("%d %d", white, black);

        }
        scanner.close();

    }

    private static long max(long a, long b) {
        return a > b ? a : b;
    }

    private static long min(long a, long b) {
        return a < b ? a : b;
    }
}

参考文章：腾讯2019秋招笔试——妞妞的问题（Java实现），文章内有图解。