Simplest Explanation | | Thought Process | | Why Bitmasking
IntuitionTo solve this problem, let's analyze the given constraints and requirements:
We have a grid of size m × n.
We can only use 3 colors to paint the grid.
# Intuition

To solve this problem, let's analyze the given constraints and requirements:

- We have a grid of size **m × n**.
- We can only use **3 colors** to paint the grid.
- No two adjacent cells (horizontally or vertically) can have the same color.

### Initial Thoughts

A brute force approach would be to assign colors to each cell one by one, ensuring no adjacent cells share the same color. However, this method involves excessive backtracking, making it inefficient.

Instead, a more structured approach is:

1. **Column-wise Coloring:** Start by filling each column sequentially while ensuring no adjacent colors are the same.
2. **Track Color Configurations Efficiently:** To avoid recomputing, store previously used column configurations and use them for future calculations.
3. **Bit Masking for Optimization:** Each column can be represented using bit masking, allowing us to encode its color pattern efficiently.

### Bit Masking Representation

Each cell can have one of three colors:

- **Red (01)**
- **Blue (10)**
- **Green (11)**

Thus, a column of `m` rows can be represented using a `2m`-bit integer. For example, if a column is `[R, B, R, G, B]`, its bit representation would be:

```
[01(R) 10(B) 01(R) 11(G) 10(B)]  →  0110011110
```

Since `m ≤ 5`, the maximum number of bits required is `10`, meaning there are at most `1024` possible column configurations.

# Approach

### Steps to Solve the Problem

1. **Start from the first column** and paint its rows according to the constraints.
2. **Recursive Traversal:** Move to the next column and continue painting while ensuring:
   - The current cell’s color differs from the left and top adjacent cells.
3. **Use Memoization:** Store results for previously computed column configurations to avoid redundant computations.
4. **Base Case:** If we reach the last column, return `1` as a valid configuration.
5. **Bit Manipulation to Extract Colors:**
   - Extract the left-adjacent cell’s color from the previous column.
   - Extract the top-adjacent cell’s color from the current column.
6. **Try all possible colors (****`1, 2, 3`****)** and recursively compute valid grid configurations.
7. **Store and Return Results:** Memoize results for each unique column configuration to improve efficiency.

# Complexity Analysis

- **Time Complexity:** Since we use bit masking and memoization to store previously computed results, the time complexity is approximately **O(n × 3^m)**, which is manageable for small values of `m` and `n`.
- **Space Complexity:** **O(n × 1024)** for memoization, as there are at most `1024` unique column configurations.

# Code Implementation

```cpp
class Solution {
public:
    long long MOD;
    vector<vector<long long>> dp;

    long long fun(long long column, long long row, long long lastcolColor, long long currcolColor, int m, int n) {
        if (row == m) {
            row = 0;
            lastcolColor = currcolColor;
            currcolColor = 0;
            return fun(column + 1, row, lastcolColor, currcolColor, m, n) % MOD;
        }
        if (column == n)
            return 1;

        if (row == 0 && dp[column][lastcolColor] != -1)
            return dp[column][lastcolColor];

        // Extract left-adjacent color
        long long isred = lastcolColor & (1LL << (2 * row));  
        long long isblue = lastcolColor & (1LL << (2 * row + 1));
        long long isgreen = isred && isblue;  
        long long leftCol = isgreen ? 3 : (isblue ? 2 : (isred ? 1 : 0));

        // Extract top-adjacent color
        long long upCol = 0;
        if (row != 0) {
            long long isred = currcolColor & (1LL << (2 * (row - 1)));  
            long long isblue = currcolColor & (1LL << (2 * (row - 1) + 1));
            long long isgreen = isred && isblue;
            upCol = isgreen ? 3 : (isblue ? 2 : (isred ? 1 : 0));
        }

        long long res = 0;
        for (long long j = 1; j <= 3; j++) {
            if (j != upCol && j != leftCol) {
                res = (res % MOD + fun(column, row + 1, lastcolColor, currcolColor | (j * (1 << (2 * row))), m, n) % MOD) % MOD;
            }
        }

        if (row == 0) dp[column][lastcolColor] = res;
        return res;
    }

    int colorTheGrid(int rows, int cols) {
        MOD = 1e9 + 7;
        dp.resize(1001, vector<long long>(1025, -1));
        return fun(0, 0, 0, 0, rows, cols);
    }
};
```

# Summary

- We used **bit masking** to efficiently store and track column color patterns.
- **Recursive DP with memoization** helps optimize redundant calculations.
- The approach ensures valid color assignments by checking adjacent constraints.
- This method is feasible for `m ≤ 5` and `n ≤ 1000` due to the optimized state space.

This approach provides an efficient way to solve the problem while ensuring optimal time and space complexity. 🚀


['C++']