1931. Painting a Grid With Three Different Colors

[mah-shamim]

Topics: Dynamic Programming

You are given two integers m and n. Consider an m x n grid where each cell is initially white. You can paint each cell red, green, or blue. All cells must be painted.

Return the number of ways to color the grid with no two adjacent cells having the same color. Since the answer can be very large, return it modulo 109 + 7.

Example 1:

• Input: m = 1, n = 1
• Output: 3
• Explanation: The three possible colorings are shown in the image above.

Example 2:

• Input: m = 1, n = 2
• Output: 6
• Explanation: The six possible colorings are shown in the image above.

Example 3:

• Input: m = 5, n = 5
• Output: 580986

Constraints:

• 1 <= m <= 5
• 1 <= n <= 1000

Hint:

1. Represent each colored column by a bitmask based on each cell color.
2. Use bitmasks DP with state (currentCell, prevColumn).

[mah-shamim]

We need to determine the number of ways to paint an m x n grid using three colors (red, green, and blue) such that no two adjacent cells (horizontally or vertically) have the same color. The result should be returned modulo 10⁹ + 7.

Approach

1. Generate Valid Column Configurations: First, generate all valid column configurations for an m-row grid where each cell in the column is colored such that no two consecutive cells have the same color. This can be done using backtracking to explore all possible valid color sequences.

2. Precompute Compatible Transitions: For each valid column configuration, determine which other configurations can follow it such that no cells in the same row of consecutive columns have the same color. This is stored in a transition matrix.

3. Dynamic Programming (DP): Use dynamic programming to compute the number of valid ways to paint the grid column by column. The DP state tracks the number of ways to paint up to the current column ending with a specific configuration. Transitions between columns are determined using the precompatible compatibility matrix.

Let's implement this solution in PHP: 1931. Painting a Grid With Three Different Colors

<?php
/**
 * @param Integer $m
 * @param Integer $n
 * @return Integer
 */
function colorTheGrid($m, $n) {
    $mod = 1000000007;
    $configs = generateConfigs($m);
    $k = count($configs);
    if ($k == 0) return 0;

    // Precompute compatible transitions
    $compatible = array();
    foreach ($configs as $i => $c1) {
        $compats = array();
        foreach ($configs as $j => $c2) {
            $valid = true;
            for ($row = 0; $row < $m; $row++) {
                if ($c1['colors'][$row] == $c2['colors'][$row]) {
                    $valid = false;
                    break;
                }
            }
            if ($valid) {
                $compats[] = $j;
            }
        }
        $compatible[$i] = $compats;
    }

    // Initialize DP
    $dp = array_fill(0, $k, 1);

    for ($col = 2; $col <= $n; $col++) {
        $new_dp = array_fill(0, $k, 0);
        foreach ($compatible as $i => $trans) {
            if ($dp[$i] == 0) continue;
            foreach ($trans as $j) {
                $new_dp[$j] = ($new_dp[$j] + $dp[$i]) % $mod;
            }
        }
        $dp = $new_dp;
    }

    $sum = array_sum($dp) % $mod;
    return $sum;
}

/**
 * @param $m
 * @return array
 */
function generateConfigs($m) {
    $configs = array();
    $current = array();
    backtrack($m, 0, -1, $current, $configs);
    return $configs;
}

/**
 * @param $m
 * @param $row
 * @param $prevColor
 * @param $current
 * @param $configs
 * @return void
 */
function backtrack($m, $row, $prevColor, &$current, &$configs) {
    if ($row == $m) {
        $num = 0;
        $pow = 1;
        foreach ($current as $color) {
            $num += $color * $pow;
            $pow *= 3;
        }
        $configs[] = array('num' => $num, 'colors' => $current);
        return;
    }
    for ($color = 0; $color < 3; $color++) {
        if ($color == $prevColor) continue;
        array_push($current, $color);
        backtrack($m, $row + 1, $color, $current, $configs);
        array_pop($current);
    }
}

// Example usage:
echo colorTheGrid(1, 1) . "\n"; // Output: 3
echo colorTheGrid(1, 2) . "\n"; // Output: 6
echo colorTheGrid(5, 5) . "\n"; // Output: 580986
?>

Explanation:

1. Generating Valid Column Configurations: The generateConfigs function uses backtracking to generate all valid column configurations where no two consecutive cells in the column have the same color. Each configuration is represented as an array of colors and an integer for efficient handling.

2. Compatibility Check: For each pair of configurations, we check if they can be adjacent columns by ensuring no two cells in the same row have the same color. This is stored in a transition matrix.

3. Dynamic Programming: The DP array dp tracks the number of ways to paint up to the current column ending with each configuration. For each subsequent column, we update the DP array using the transition matrix to sum valid transitions from the previous column.

This approach efficiently computes the result using dynamic programming and precomputed transitions, ensuring we handle up to the maximum constraints efficiently.

[topugit]

Thanks for solving the problem of "Painting a Grid With Three Different Colors"

[mah-shamim]

Thanks