链接：https://ac.nowcoder.com/acm/contest/53284/J 来源：牛客网 给你一个M*N的网格，用红绿蓝（RGB）三种颜色填充，使得任意两个相邻的格子（上下左右四个方向相邻）颜色不同，请问总共有多少种不同的涂色方案？

这是一个经典的图论问题，可以使用染色法来解决。具体来说，我们可以从任意一个格子开始，将其染成红色，然后将其相邻的格子染成绿色，再将与绿色格子相邻的格子染成蓝色，以此类推。这样染色的过程中，每个格子的颜色都只与其相邻的格子有关，因此不会出现相邻格子颜色相同的情况。

根据染色法的思路，我们可以得到一个递推式：设f[i][j][k]表示第i行第j列的格子染成颜色k（k=0表示红色，k=1表示绿色，k=2表示蓝色）的涂色方案数，则有：

f[i][j][0] = f[i-1][j][1] + f[i-1][j][2] + f[i][j-1][1] + f[i][j-1][2]
f[i][j][1] = f[i-1][j][0] + f[i-1][j][2] + f[i][j-1][0] + f[i][j-1][2]
f[i][j][2] = f[i-1][j][0] + f[i-1][j][1] + f[i][j-1][0] + f[i][j-1][1]

其中，第一行和第一列的格子需要特殊处理，即：

f[1][j][0] = f[1][j-1][1] + f[1][j-1][2]
f[1][j][1] = f[1][j-1][0] + f[1][j-1][2]
f[1][j][2] = f[1][j-1][0] + f[1][j-1][1]

f[i][1][0] = f[i-1][1][1] + f[i-1][1][2]
f[i][1][1] = f[i-1][1][0] + f[i-1][1][2]
f[i][1][2] = f[i-1][1][0] + f[i-1][1][1]

最终的答案即为f[m][n][0] + f[m][n][1] + f[m][n][2]。

这个问题可以用动态规划来解决，具体实现可以参考以下代码：

int f[105][105][3];

int main() {
int m, n;
scanf("%d%d", &m, &n);
memset(f, 0, sizeof(f));
f[1][1][0] = f[1][1][1] = f[1][1][2] = 1;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (i == 1 && j == 1) continue;
f[i][j][0] = f[i-1][j][1] + f[i-1][j][2] + f[i][j-1][1] + f[i][j-1][2];
f[i][j][1] = f[i-1][j][0] + f[i-1][j][2] + f[i][j-1][0] + f[i][j-1][2];
f[i][j][2] = f[i-1][j][0] + f[i-1][j][1] + f[i][j-1][0] + f[i][j-1][1];
f[i][j][0] %= MOD;
f[i][j][1] %= MOD;
f[i][j][2] %= MOD;
}
}
printf("%d\n", (f[m][n][0] + f[m][n][1] + f[m][n][2]) % MOD);
return 0;
}