Today I have done leetcode's May LeetCoding Challenge with cpp.

May LeetCoding Challenge 18

Description

Painting a Grid With Three Different Colors

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

Solution

class Solution {
  const int MOD = 1e9 + 7;
public:
  int colorTheGrid(int m, int n) {
    int target = pow(3, m);
    vector<vector<int>> pattern(target, vector<int>(m));
    for(int i = 0; i < target; ++i) {
      int current = i;
      for(int col = 0; col < m; ++col) {
        pattern[i][col] = current % 3;
        current /= 3;
      }
    }
    vector<int> validCol;
    for(int i = 0; i < target; ++i) {
      bool ok = true;
      for(int col = 1; col < m && ok; ++col) {
        ok = (pattern[i][col] != pattern[i][col - 1]);
      }
      if(ok) validCol.push_back(i);
    }
    vector<vector<bool>> validAdjacent(target, vector<bool>(target));
    for(auto i : validCol) {
      for(auto j : validCol) {
        bool ok = true;
        for(int col = 0; col < m && ok; ++col) {
          ok = (pattern[i][col] != pattern[j][col]);
        }
        if(ok) validAdjacent[i][j] = true;
      }
    }

    vector<vector<int>> dp(2, vector<int>(target, 1));
    for(int col = 2; col <= n; ++col) {
      int parity = col & 1;
      for(auto i : validCol) {
        dp[parity][i] = 0;
        for(auto j : validCol) {
          if(!validAdjacent[i][j]) continue; 
          dp[parity][i] += dp[!parity][j];
          dp[parity][i] %= MOD;
        }
      }
    }
    int answer = 0;
    for(auto i : validCol) {
      answer += dp[n & 1][i];
      answer %= MOD;
    }
    return answer;
  }
};

// Accepted
// 84/84 cases passed (72 ms)
// Your runtime beats 48.9 % of cpp submissions
// Your memory usage beats 85.16 % of cpp submissions (10.1 MB)