C++程式中N×3網格的塗色方法數

假設我們有一個大小為n x 3的網格，我們想用三種顏色中的每一種來塗色網格的每個單元格。這裡使用的顏色是紅色、黃色和綠色。

現在有一個約束條件，即不允許兩個相鄰的單元格具有相同的顏色。網格有n行。最後，我們必須找到可以塗色此網格的方法數。答案可能非常大，因此返回它模10^9 + 7的結果。

因此，如果輸入是1，則輸出將為12。

為了解決這個問題，我們將遵循以下步驟：

  • m = 10^9 + 7

  • 定義一個函式add()，它將接收a, b,

  • 返回((a mod m) + (b mod m)) mod m

  • 從主方法執行以下操作：

  • a123 := 6, a121 = 6

  • 初始化i := 2，當i −= n時，更新（將i增加1），執行：

    • b121 := add(3 * a121, 2 * a123)

    • b123 := add(2 * a121, 2 * a123)

    • a121 := b121

    • a123 := b123

  • 返回add(a123, a121)

示例

讓我們看看下面的實現，以便更好地理解：

線上演示

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const lli mod = 1e9 + 7;
class Solution {
public:
   lli add(lli a, lli b){
      return ((a % mod) + (b % mod)) % mod;
   }
   int numOfWays(int n){
      lli a123 = 6, a121 = 6;
      lli b123, b121;
      for (int i = 2; i <= n; i++) {
         b121 = add(3 * a121, 2 * a123);
         b123 = add(2 * a121, 2 * a123);
         a121 = b121;
         a123 = b123;
      }
      return add(a123, a121);
   }
};
main(){
   Solution ob;
   cout << (ob.numOfWays(3));
}

輸入

3

輸出

246

更新於：2020年7月21日

114 次瀏覽

開啟你的職業生涯

透過完成課程獲得認證

開始學習
廣告