最大化数组中矩形的覆盖范围

Question

我的任务如下：

输入：

0 0 1 0 0 1 0 0 1 1 1 1 1 0 0 1 1 0 0 1 0 0 1 1 1 1 1 0 0 0 1 0 0 1 0

其中0s表示苹果树，1s表示香蕉树

亚历克斯想保留所有的苹果树，而贝雷特想保留香蕉树。转移一棵树的所有权的成本是1美元。

找到最好的起始矩形，使成本尽可能低。

此示例的解决方案如下：

​

产出：$6 (用于转移6棵树的所有权)

最大执行时间为1.0s，输入为1n和m是果园的大小

任何帮助都将不胜感激！:)

Answer 1

除非对运行时间或整体方法有特殊要求，否则可以使用一个相当简单的解决方案:对于每个可能的矩形，检查必须移动多少棵树。这可以通过4个嵌套的for循环和一些实用方法来完成。

下面是一个MCVE (我没有对它进行彻底的测试，但它应该显示了一般的方法)

public class OptimizeRectangle
{
    public static void main(String[] args)
    {
        int array[][] =
        {
            { 0, 0, 1, 0, 0, 1, 0 }, 
            { 0, 1, 1, 1, 1, 1, 0 }, 
            { 0, 1, 1, 0, 0, 1, 0 },
            { 0, 1, 1, 1, 1, 1, 0 }, 
            { 0, 0, 1, 0, 0, 1, 0 },
        };
        optimize(array);
    }

    private static void optimize(int array[][])
    {
        int rows = array.length;
        int cols = array[0].length;
        int ones = count(array, 0, 0, rows, cols, 1);
        int bestR0 = 0;
        int bestC0 = 0;
        int bestR1 = 0;
        int bestC1 = 0;
        int minToMove = Integer.MAX_VALUE;
        for (int r0=0; r0<rows; r0++)
        {
            for (int c0=0; c0<cols; c0++)
            {
                for (int r1=r0+1; r1<=rows; r1++)
                {
                    for (int c1=c0+1; c1<=cols; c1++)
                    {
                        int zerosInRect = count(array, r0, c0, r1, c1, 0);
                        int onesInRect = count(array, r0, c0, r1, c1, 1);
                        int toMove = 
                            (ones - onesInRect) + zerosInRect;
                        if (toMove < minToMove)
                        {
                            minToMove = toMove;
                            bestR0 = r0;
                            bestC0 = c0;
                            bestR1 = r1;
                            bestC1 = c1;
                        }
                    }
                }
            }
        }
        System.out.println("Input");
        System.out.println(toString(array));

        int a[][] = copy(array);
        set(a, bestR0, bestC0, bestR1, bestC1, -1);
        System.out.println("Result");
        System.out.println(toString(a));
    }

    private static String toString(int array[][])
    {
        int rows = array.length;
        int cols = array[0].length;
        StringBuilder sb = new StringBuilder();
        for (int r=0; r<rows; r++)
        {
            for (int c=0; c<cols; c++)
            {
                if (array[r][c] >= 0)
                {
                    sb.append(array[r][c]+" ");
                }
                else
                {
                    sb.append("  ");
                }
            }
            sb.append("\n");
        }
        return sb.toString();
    }

    private static int[][] copy(int array[][])
    {
        int result[][] = new int[array.length][];
        for (int i=0; i<array.length; i++)
        {
            result[i] = array[i].clone();
        }
        return result;
    }

    private static void set(int array[][], 
        int r0, int c0, int r1, int c1, int value)
    {
        for (int r=r0; r<r1; r++)
        {
            for (int c=c0; c<c1; c++)
            {
                array[r][c] = value;
            }
        }
    }

    private static int count(int array[][], 
        int r0, int c0, int r1, int c1, int value)
    {
        int count = 0;
        for (int r=r0; r<r1; r++)
        {
            for (int c=c0; c<c1; c++)
            {
                if (array[r][c] == value)
                {
                    count++;
                }
            }
        }
        return count;
    }

}