Свести к минимуму затраты на покрытие пола плиткой размером 1*1 и 1*2.

Дан двумерный массив arr[][] размера N*M , состоящий из '.' и '*', представляющие пол, и два положительных целых числа A и B , представляющие стоимость плитки 1*1 и 1*2 соответственно, задача состоит в том, чтобы заполнить все символы, имеющие '.' на полу плиткой размером 1*1 или 1*2 таким образом, чтобы затраты на заливку пола были минимальны и не допускалось переворачивание плитки.

Примеры:

Input: A = 2, B = 10, arr[][] = {{‘.’, ‘.’, ‘*’},  {‘.’, ‘*’, ‘*’}}
Output: 6
Explanation:
Cover arr[0][0] with 1*1 tile, arr[0][1] with 1*1 tile and arr[1][0] with 1*1 tile.
Therefore, the minimum cost is 2 + 2 +2 = 6.

Input: A = 2, B = 6, arr[][] = {{‘.’, ‘.’, ‘.’}, {‘*’, ‘*’, ‘.’}, {‘.’, ‘.’, ‘*’}}
Output: 12

Подход: Данная проблема может быть решена с использованием жадного подхода. Идея состоит в том, чтобы пройти по заданному 2D-массиву построчно, и если два последовательных '.' встречается, затем выберите плитку с минимальной стоимостью размещения двух плиток 1 * 1 или одной плитки 1 * 2 . Выполните следующие шаги, чтобы решить проблему:

• Инициализируйте переменную, скажем , как 0 , чтобы сохранить минимальную общую стоимость.
• Пройдите по заданному 2D-массиву arr[][] по строкам, используя i для индекса строки и j для индекса столбца, и выполните следующие шаги:
  • Если значение arr[i][j] равно '*' , то продолжаем итерацию.
  • В противном случае проверьте следующие условия:
    • Если значение j равно m(M – 1) , то добавьте A к переменной ans .
    • В противном случае, если значение (arr[i][j + 1]) равно '.' , затем добавьте минимум значений 2*A и B к переменной ans .
    • Во всех остальных случаях добавьте значение A к переменной ans .
• После выполнения вышеуказанных шагов выведите в качестве результата значение ans .

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N * M)
Вспомогательное пространство: O(1)