一、题目描述

1591. 奇怪的打印机 II

给你一个奇怪的打印机，它有如下两个特殊的打印规则：

每一次操作时，打印机会用同一种颜色打印一个矩形的形状，每次打印会覆盖矩形对应格子里原本的颜色。
一旦矩形根据上面的规则使用了一种颜色，那么 相同的颜色不能再被使用 。
给你一个初始没有颜色的 m x n 的矩形 targetGrid ，其中targetGrid[row][col] 是位置 (row, col) 的颜色。

如果你能按照上述规则打印出矩形targetGrid，请你返回 true ，否则返回 false 。

二、思路分析

打印机

• 本题考查的就是贪心算法！有一点需要注意的是我们在打印颜色时需要从外至内进行打印。否则会导致内部颜色打印失效。

• 只有保持这个维度才能确保外部被打乱的颜色可以被打印机打印。因为打印机的两个特性：一次打印矩形+一个颜色只能用一次

• 换句话说不通颜色我们可以理解成不同卡片叠加在一起产生的效果。最底层的就是我们最外层的颜色。只有这样最小的最上层才会被重新渲染。

判断

• 但是本题并不是让我们去实现打印机打印的过程。仅仅是要求我们对m*n矩阵进行判断！既然是判断是否满足这个奇葩的打印机那就稍微简单一点。
• 首先外层的图层我们不需要考虑，我们只需要优先考虑内层是否满足打印需求即可

• 上图中黑框圈中的就是我们说的最外层！最内层我们分析下打印机是无法打印的，所以上述情况就是不满足打印条件。
• 关于是否满足打印的判断也很简单。只需要判断内层矩阵内是否是同一颜色即可。

• 那么这种情况根据上面我说的判断依据进行判断好像是不通过的。但是这种情况很明显是可以打印的。
• 上面也说了需要从内置外。我们只需要先进行判断如果最内层不满足则整体不满足。最外层不需要关心，因为对第一层打印全是红色，等到对第二层打印后就会出现上面情况。所以这里需要仔细思考下！

for (Map.Entry<Integer, Direction> entry : entries) {
    Integer key = entry.getKey();
    if (sameColorAndPrintMark(key, entry.getValue(), targetGrid)) {
        value=key;
        break;
    }
}

• 我们只需要对当前颜色组进行判断就可以了！最后通过对value进行判断能够删选出内层满足条件的颜色块。将颜色块从颜色集合中剔除。然后在重复此操作就可以了。

渲染

• 上面我们说了判断的依据。但是在代码中出现一个sameColorAndPrintMark方法。该方法是判断区间内是否颜色相同并进行打印标记的。因为颜色取值是[1,60]。所以我们这里使用0来标记已经被其他色块打印过 。然后在判断是否是同一色块时过滤掉已经被渲染色块在进行判断如果不通过则真的无法通过了。

• 上面这种情况我们在判断浅蓝色的时候通过，当进行判断橙色色块时是不通过的。因为他的范围内包含了除了已经被渲染的蓝色以外还有未被渲染的红色。所以这种情况是不能被打印的。

private boolean sameColorAndPrintMark(Integer key, Direction direction, int[][] targetGrid) {
    for (int i = direction.top; i <= direction.bottom; i++) {
        for (int j = direction.left; j <= direction.right; j++) {
            if(targetGrid[i][j]!=0&&targetGrid[i][j]!=key)
                return false;
        }
    }
    for (int i = direction.top; i <= direction.bottom; i++) {
        for (int j = direction.left; j <= direction.right; j++) {
            targetGrid[i][j] = 0;
        }
    }
    return true;
}

• 最终我们一直重复渲染的步骤，直到所有的版块都被标记打印了。当然对于本身就不满足打印的情况就一直不会出现全部被标记的情况这种情况岂不是一种重复下去。这样程序不就死循环了吗
• 当然我们不允许这种情况发生。我们在渲染结束后需要进行判断如果在针对剩余的色块进行渲染时没有一块可以进行渲染，那么我们就直接判定不满足情况

if (value == -1) {
    return false;
} else {
    //剔除
    colorMap.remove(value);
}

三、AC代码

• 在上面分析的过程我已经基本将AC代码暴露出来了。我是通过不同的情况讲解出了各个代码的作用。我觉得这样更加的有利于我们理解他的作用。现在我放出完成的代码供读者们参考！！！

class Direction{
    int left = 61;
    int right = -1;
    int top = 61;
    int bottom = -1;
}
public boolean isPrintable(int[][] targetGrid) {
    int[] values=new int[61];
    int n=targetGrid.length, m=targetGrid[0].length;
    Map<Integer,Direction> colorMap = new HashMap<>();
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            int val=targetGrid[i][j];
            Direction direction = null;
            if (colorMap.containsKey(val)) {
                direction = colorMap.get(val);
            } else {
                direction = new Direction();
                colorMap.put(val,direction);
            }
            direction.left = Math.min(direction.left, j);
            direction.right = Math.max(direction.right, j);
            direction.top = Math.min(direction.top, i);
            direction.bottom = Math.max(direction.bottom, i);
        }
    }
    while (!isAllPrint(targetGrid)) {
        int value=-1;
        Set<Map.Entry<Integer, Direction>> entries = colorMap.entrySet();
        for (Map.Entry<Integer, Direction> entry : entries) {
            Integer key = entry.getKey();
            if (sameColorAndPrintMark(key, entry.getValue(), targetGrid)) {
                value=key;
                break;
            }
        }
        if (value == -1) {
            return false;
        } else {
            //剔除
            colorMap.remove(value);
        }
    }
    return true;
}

private boolean isAllPrint(int[][] targetGrid) {
    for (int i = 0; i < targetGrid.length; i++) {
        for (int j = 0; j < targetGrid[i].length; j++) {
            if (targetGrid[i][j]!=0) {
                return false;
            }
        }
    }
    return true;
}

private boolean sameColorAndPrintMark(Integer key, Direction direction, int[][] targetGrid) {
    for (int i = direction.top; i <= direction.bottom; i++) {
        for (int j = direction.left; j <= direction.right; j++) {
            if(targetGrid[i][j]!=0&&targetGrid[i][j]!=key)
                return false;
        }
    }
    for (int i = direction.top; i <= direction.bottom; i++) {
        for (int j = direction.left; j <= direction.right; j++) {
            targetGrid[i][j] = 0;
        }
    }
    return true;
}

四、总结

• 此题比较有意思的是需要分层考虑打印问题！从外至内进行打印渲染。但是因为不确定因素所以我们一次渲染无法最终得出结果，所以需要我们进行多次渲染。

• 但是需要多少次我们也无法确定，这时候我们就一直渲染！但是不能一直渲染所以我们每次渲染后需要对是否需要继续下去进行判定

• 当然笔者这里也不是一番风顺的，提交过程也是不断的试错调试。这里我只是想告诉读者们刷题需要不断努力，不要因为错误而放弃

这里点个赞、关个注呗！持续贡献原创文章！如果你觉得那个算法有意思，下方告诉我，我去试试能否攻克！！！