题目：Print

题目意思：你有一个网格大小n×3，你想用三种颜色中的一种来绘制网格的每个单元:红色，黄色或绿色，同时确保没有两个相邻的单元具有相同的颜色(没有两个单元共享垂直或水平边具有相同的颜色)。

思路：动态规划

1. 网格横向只有3个格子，可以考虑暴力统计一行中可填入颜色的方案数
2. 同时，还要确保纵向相邻格子颜色不能一样。同样可暴力统计上一行填入的颜色后当前行可以填入颜色的合法方案数，总的时间复杂度为O(3^3*3^3*n)

代码如下：

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;

public class Main {
	//快速输入
	static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
	//快速输出
	static PrintWriter pw=new PrintWriter(new OutputStreamWriter(System.out));
	
	public static void main(String[] args) throws IOException {
		String[] s=br.readLine().split(" ");
		int n=Integer.parseInt(s[0]);
		int p=(int) (Math.pow(10, 9)+7);
		//记录每一行每一格子填入某种颜色的方案数，0代表红、1代表黄、2代表绿，例如dp[0][0][1][2]，代表第一行的格子分别填入红黄绿
		long[][][][] dp=new long[n][3][3][3];
		//初始化第一行
		for(int i=0;i<3;i++) {
			for(int j=0;j<3;j++) {
				for(int k=0;k<3;k++) {
					if(i==j||j==k) {
						continue;
					}
					dp[0][i][j][k]=1;
				}
			}
		}
		for(int r=1;r<n;r++) {
			for(int i=0;i<3;i++) {
				for(int j=0;j<3;j++) {
					for(int k=0;k<3;k++) {
						//行内颜色填入相邻不能相同
						if(i==j||j==k) {
							continue;
						}
						//根据上一行颜色的方案数更新当前行填入颜色的方案数
						for(int ii=0;ii<3;ii++) {
							for(int jj=0;jj<3;jj++) {
								for(int kk=0;kk<3;kk++) {
									if(ii==jj||jj==kk) {
										continue;
									}
									if(ii==i||jj==j||kk==k) {
										continue;
									}
									dp[r][i][j][k]=(dp[r][i][j][k]+dp[r-1][ii][jj][kk])%p;
								}
							}
						}
					}
				}
			}
		}
		long ans=0;
		//最后一行合法的颜色填入方案数之和就是答案
		for(int i=0;i<3;i++) {
			for(int j=0;j<3;j++) {
				for(int k=0;k<3;k++) {
					if(i==j||j==k) {
						continue;
					}
					ans=(ans+dp[n-1][i][j][k])%p;
				}
			}
		}
		pw.println(ans);
		pw.flush();
	}
}