Problem Statement
Painting a Grid
You are a game designer working on a puzzle game where players need to color a grid with three different colors. The challenge is to color the grid such that no adjacent cells have the same color.
Given two integers m and n, you need to count the number of ways to paint an m × n grid with three colors (red, green, and blue) such that no adjacent cells have the same color. Two cells are considered adjacent if they share a side.
Since the answer may be very large, return it modulo 10^9 + 7.
Examples
Example 1:
Input: m = 1, n = 1
Output: 3
Explanation: We can paint the single cell with any of the three colors: red, green, or blue.
Example 2:
Input: m = 1, n = 2
Output: 6
Explanation: We can paint the grid in 6 ways: [red, green], [red, blue], [green, red], [green, blue], [blue, red], [blue, green].
Example 3:
Input: m = 5, n = 3
Output: 580986
Explanation: There are 580986 ways to paint the 5 × 3 grid with the given constraints.
Constraints
- 1 <= m <= 5
- 1 <= n <= 1000
- The answer is guaranteed to be in the range [1, 10^9 + 7].
Problem Breakdown
To solve this problem, we need to:
- The key insight is to use dynamic programming with state compression to solve this problem efficiently.
- We can represent the state of each column using a bitmask, where each bit represents the color of a cell.
- For each valid state of a column, we need to find all valid states for the next column.
- A state transition is valid if no adjacent cells have the same color, both horizontally and vertically.
String Problems
Learning Objective
Apply string manipulation concepts to solve a real-world problem.
Painting a Grid
You are a game designer working on a puzzle game where players need to color a grid with three different colors. The challenge is to color the grid such that no adjacent cells have the same color.
Given two integers m and n, you need to count the number of ways to paint an m × n grid with three colors (red, green, and blue) such that no adjacent cells have the same color. Two cells are considered adjacent if they share a side.
Since the answer may be very large, return it modulo 10^9 + 7.
Examples
Example 1:
We can paint the single cell with any of the three colors: red, green, or blue.
Example 2:
We can paint the grid in 6 ways: [red, green], [red, blue], [green, red], [green, blue], [blue, red], [blue, green].
Example 3:
There are 580986 ways to paint the 5 × 3 grid with the given constraints.
Problem Breakdown
Constraints:
- 1 <= m <= 5
- 1 <= n <= 1000
- The answer is guaranteed to be in the range [1, 10^9 + 7].
Key Insights:
The key insight is to use dynamic programming with state compression to solve this problem efficiently.
We can represent the state of each column using a bitmask, where each bit represents the color of a cell.
For each valid state of a column, we need to find all valid states for the next column.
A state transition is valid if no adjacent cells have the same color, both horizontally and vertically.
Real-World Application
This problem has several practical applications:
Game Design
Used in puzzle games where players need to color grids with specific constraints.
Map Coloring
Similar to the map coloring problem in cartography, where adjacent regions must have different colors.
Visual Design
Used in creating visually appealing patterns with color constraints for design purposes.