This is the 18th day of my participation in the More text Challenge. For more details, see more text Challenge

1. Description of the topic

Strange printer II

Here’s a weird printer that has two special printing rules:

Each time, the printer prints a rectangular shape in the same color, each print overwriting the original color of the rectangle’s corresponding cell. Once the rectangle has used one color according to the above rules, the same color cannot be used again. Give you an m x N rectangle targetGrid with no initial color, where targetGrid[row][COL] is the color of the position (row, COL).

Return true if you can print the rectangular targetGrid as described above, false otherwise.

Second, thinking analysis

The printer

  • The greedy algorithm! One thing to note is that we need to print colors from the outside in. Otherwise, the internal color printing will fail.

  • Maintaining this dimension is the only way to ensure that the outer colors that are scrambled can be printed by the printer. Because of the two characteristics of the printer: print a rectangle + a color can only be used once

  • In other words, instead of color, we can think of it as the effect of different cards stacked on top of each other. The bottom layer is our outermost color. Only then will the smallest top layer be rerendered.

judge

  • But this is not asking us to implement the printer printing process. It just requires us to be rightm*nMatrix to judge! It’s a little bit easier to decide if this weird printer is going to work.
  • First of all, we don’t need to worry about the outer layer, we just need to prioritize whether the inner layer meets the printing needs

  • The black circle in the picture above is what we call the outermost layer! The innermost layer of our analysis of the printer is unable to print, so the above situation is not to meet the printing conditions.
  • The decision about whether to print is simple. You just need to determine whether the inner matrix is the same color.

  • So this is a case where it doesn’t seem to pass on the basis of what I said above. But in this case it’s obviously printable.
  • It also says you need to go from inside to outside. We just have to make the judgment that if the innermost layer doesn’t satisfy then the whole thing doesn’t satisfy. You don’t need to worry about the outer layer, because the first layer is all red, and the second layer will be the same. So think carefully here!
for (Map.Entry<Integer, Direction> entry : entries) {
    Integer key = entry.getKey();
    if (sameColorAndPrintMark(key, entry.getValue(), targetGrid)) {
        value=key;
        break; }}Copy the code
  • We only need to judge the current color group can be! Finally, the color blocks that meet the conditions in the inner layer can be deleted and selected by judging the value. Removes the color block from the color set. Then repeat the operation.

Apply colours to a drawing

  • Above we said the basis of judgment. But one appears in the codesameColorAndPrintMarkMethods. This method is to judge whether the color of the interval is the same and print the mark. Because the color value is [1,60]. So we use 0 here to mark that it has been printed by another color block. Then, when judging whether it is the same color block, the rendered color block is filtered out. If it does not pass, it really cannot pass.

  • In this case we passed the light blue, but we didn’t pass the orange. Because his range includes the unrendered red in addition to the rendered blue. So you can’t print in this case.
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;
}
Copy the code
  • Finally we repeat the render steps until all the sections are marked and printed. Of course, for itself is not enough to print the case has not been all marked this situation is not a repeat. Wouldn’t that be an infinite loop
  • Of course we can’t allow that to happen. We need to make a judgment after rendering if none of the remaining color blocks can be rendered when we render them, then we will directly determine that the case is not satisfied
if (value == -1) {
    return false;
} else {
    / / remove
    colorMap.remove(value);
}
Copy the code

Three, AC code

  • I’ve basically exposed the AC code in the above analysis. I’ve explained what each code does in different situations. I think it’s better for us to understand his role. Now I release the finished code for your reference!!
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 = newDirection(); 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 {
            / / removecolorMap.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;
}
Copy the code

Four,

  • This problem is more interesting is the need to consider the hierarchical printing problem! Print and render from the outside in. However, due to uncertainties, we can’t get the final result in one render, so we need to render several times.

  • But we can’t be sure how many times, so we just keep rendering! But we can’t render all the time so we have to decide after each render whether we want to continue or not

  • Of course, it wasn’t easy here, and the submission process was trial and error. Here I just want to tell the readers to brush questions need to keep working hard, do not give up because of mistakes

Here click a like, close a note! Continue to contribute original articles! If you find that algorithm interesting, let me know below, I will see if I can conquer it!!