能否完美地拼成矩形

题目:每条边不是平行于X轴就是平行于Y轴的矩形,可以用左下角点和右上角的点来表示。比如:{1,2,3,4},表示的图形如图
能否完美地拼成矩形
给定一个n行4列的二维数组matrix,表示n个每条边不是平行于X轴就是平行于Y轴的矩形。想知道所有的矩形能否组成一个大的完美矩形。完美矩形是指拼出的整体图案是矩形,既不缺任何块儿,也没有重合的部分。
例:matrix={
{1,1,3,3},
{3,1,4,2}
{1,3,2,4}
{3,2,4,4}
}
返回false.如果画出这四个矩形,会发现拼出的图案缺少{2,3,3,4}这一块儿。

分析:

能否完美地拼成矩形
由Left,Right,Up,Down可以定位一个大矩形,面积为(Right-Left)*(Up-Down)
所以:
每一个小矩形的面积累加起来必须等于大矩形的面积
除大矩形的四个顶点只出现一次外,其他任何小矩形的顶点都必须出现偶数次。
能否完美地拼成矩形

代码实现:

import java.util.HashSet;

public class PrefectRectangle {
    public static boolean isPrefectRectangle(int[][] matrix) {
        if (matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        int Left = Integer.MAX_VALUE;
        int Right = Integer.MIN_VALUE;
        int Up = Integer.MIN_VALUE;
        int Down = Integer.MAX_VALUE;
        HashSet<String> set = new HashSet<>();
        int area = 0;
        for (int[] rectangle : matrix) {
            Left = Math.min(rectangle[0], Left);
            Down = Math.min(rectangle[1], Down);
            Right = Math.max(rectangle[2], Right);
            Up = Math.max(rectangle[3], Up);
            area = area + (rectangle[2] - rectangle[0]) * (rectangle[3] - rectangle[1]);
            String leftDown = rectangle[0] + "_" + rectangle[1];
            String leftUp = rectangle[0] + "_" + rectangle[3];
            String rightDown = rectangle[2] + "_" + rectangle[1];
            String rightUp = rectangle[2] + "_" + rectangle[3];
            if (!set.add(leftDown)) {
                set.remove(leftDown);
            }
            if (!set.add(leftUp)) {
                set.remove(leftUp);
            }
            if (!set.add(rightDown)) {
                set.remove(rightDown);
            }
            if (!set.add(leftUp)) {
                set.remove(leftUp);
            }
        }
        if (!set.contains(Left + "_" + Down) || !set.contains(Left + "_" + Up) || !set.contains(Right + "_" + Down) || !set.contains(Right + "_" + Up) || set.size() != 4) {
            return false;
        }
        return area == (Right - Left) * (Up - Down);
    }

    public static void main(String[] args) {
        int[][] matrix = {{1, 1, 3, 3},
                {3, 1, 4, 2},
                {1, 3, 2, 4},
                {3, 2, 4, 4},
        };
        System.out.println(isPrefectRectangle(matrix));
    }
}

运行结果:
能否完美地拼成矩形

上一篇:夜光带你走进C#语言 基础版本(46)


下一篇:85 - Maximal Rectangle