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 次浏览

开启你的职业生涯

通过完成课程获得认证

开始学习
广告