Это 18-й день моего участия в Gengwen Challenge.Подробности о мероприятии:Обновить вызов

1. Описание темы

1591. Странный Принтер II

Вот странный принтер с двумя особыми правилами печати:

В каждой операции принтер будет печатать прямоугольную форму одним и тем же цветом, и каждый отпечаток перезапишет исходный цвет в соответствующей сетке прямоугольника. Как только прямоугольник использует цвет в соответствии с приведенными выше правилами, этот же цвет нельзя использовать снова. дает вам прямоугольник m x n без цвета изначальноtargetGrid,в targetGrid[row][col] — цвет в позиции (строка, столбец).

Если вы можете распечатать прямоугольник в соответствии с приведенными выше правиламиtargetGrid, верните true , иначе верните false .

2. Анализ мыслей

принтер

Этот вопрос исследует жадный алгоритм! Следует отметить, что при печати цветов нам нужно печатать снаружи внутрь. В противном случае внутренняя цветная печать не удастся.

Только сохранение этого размера гарантирует, что внешне зашифрованные цвета могут быть напечатаны принтером. Из-за двух характеристик принтера: один прямоугольник печати + один цвет можно использовать только один раз.
Другими словами, разные цвета можно понимать как результат сложения разных карт вместе. Нижний слой — это наш внешний цвет. Только тогда будет повторно визуализирован самый маленький верхний слой.

судить

Но этот вопрос не для нас, чтобы реализовать процесс печати на принтере. просто просит насm*nМатрица судить! Так как судить о том, доволен ли этот замечательный принтер, немного проще.
Прежде всего, нам не нужно рассматривать внешний слой, нам нужно только отдать приоритет тому, соответствует ли внутренний слой потребностям печати.

Черная рамка на картинке выше — это то, что мы называем самым внешним слоем! В самом внутреннем слое мы анализируем, что принтер не может печатать, поэтому описанная выше ситуация не соответствует условиям печати.
Суждение о том, удовлетворена ли печать, также просто. Нужно только судить, одного ли цвета внутренняя матрица.

Таким образом, в этом случае кажется, что суждение, основанное на упомянутом выше основании суждения, не проходит. Но этот случай явно печатный.
Выше также сказано, что его нужно строить снаружи. Нам нужно только сначала судить, не удовлетворен ли самый внутренний слой, не удовлетворено ли целое. Самый внешний слой не нужно беспокоить, потому что первый слой напечатан красным цветом, и вышеописанная ситуация произойдет после печати второго слоя. Так что тут нужно хорошенько подумать!

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

Нам нужно только оценить текущую цветовую группу! Наконец, оценивая значение, можно удалить цветовые блоки, соответствующие условиям во внутреннем слое. Удалите цветовой блок из набора цветов. Затем повторите эту операцию.

оказывать

Мы обсудили основание для решения выше. Но в коде есть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);
}

3. Код переменного тока

В процессе приведенного выше анализа я в основном раскрыл код 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;
}

4. Резюме

Более интересным в этом вопросе является то, что он должен рассматривать проблему печати слоями! Рендеринг печати снаружи внутрь. Однако из-за неопределенных факторов мы не можем получить окончательный результат за один рендеринг, поэтому нам необходимо выполнить несколько рендерингов.
Но мы не можем быть уверены, сколько раз это займет, поэтому мы просто продолжаем рендеринг! Но он не может рендериться все время, поэтому нам нужно решить, нужно ли нам продолжать после каждого рендеринга.
Конечно у автора тут не все гладко, процесс подачи это тоже постоянная отладка методом проб и ошибок. Здесь я просто хочу сказать читателям, что нужно продолжать упорно работать, не сдаваться из-за ошибок.

Ставьте лайк и подписывайтесь сюда! Продолжайте публиковать оригинальные статьи! Если вы считаете этот алгоритм интересным, дайте мне знать ниже, и я постараюсь его преодолеть! ! !