当前位置:首页 » Project Euler » 详细页

Tri-colouring a triangular grid 题号:189 难度: 70 中英对照

Consider the following configuration of 64 triangles:

We wish to colour the interior of each triangle with one of three colours: red, green or blue, so that no two neighbouring triangles have the same colour. Such a colouring shall be called valid. Here, two triangles are said to be neighbouring if they share an edge.
Note: if they only share a vertex, then they are not neighbours.

For example, here is a valid colouring of the above grid:

A colouring C' which is obtained from a colouring C by rotation or reflection is considered distinct from C unless the two are identical.

How many distinct valid colourings are there for the above configuration?


Solution

动态规划即可。 要考虑两个递推关系,其一是已知上一层向上的正三角的颜色分布,求答案,其二是根据当前层的向下的倒三角的颜色分布求答案。 对于第一递推式,有一个分支情况是根据上一层正三角颜色,当前层的倒三角颜色有$2^{len}$种情况,需要利用第二递推式计算。 对于第二递推式,先根据上一层倒三角颜色分布将本层正三角颜色分布填充满,填充完整后调用第一递推式求和即可。

Code


public final class p189 {
    public static void main(String[] args) {
        long start=System.nanoTime();
        String result = run();        
        long end=System.nanoTime();
        System.out.println(result);
        System.out.println( (end-start)/1000000 + "ms" );
    }
    
    static public String run() {
		return ""+solve("",8);
    }

	static long[][] count = new long[9][];
	//第一递推式
	public static long solve(String in, int limit) // in = AAA
	{
		long result = 0;
		int len = in.length();
		if (count[len] == null)//记忆化工作
			count[len] = new long[pow(3, len)];
		if (len == 0) {
			result += solve("0", limit);
			result += solve("1", limit);
			result += solve("2", limit);
		} else if (len < limit) {
			char[] above = in.toCharArray(); // above = AAA
			int z = 0;
			int inverted = 0;
			for (int i = 0; i < len; i++) {
				z = z * 3;
				z = z + ((3 - (above[0]) + (above[i])) % 3);
				inverted = inverted * 3;
				inverted = inverted
						+ ((3 - (above[len - 1]) + (above[len - 1 - i])) % 3);
			}
			z = Math.min(z, inverted);
			if (count[len][z] == 0) {
				for (int i = 0; i < pow(2, len); i++) {
					char[] below = new char[len]; // below = VVV
					int k = i;
					for (int j = 0; j < len; j++) {
						int add = k % 2;
						k = k >> 1;
						below[j] = (char) ((above[j] + 1 + add) % 3 + '0');
					}
					result += solveB("", below, limit);
				}
				count[len][z] = result;
			} else
				result = count[len][z];
		} else {
			result += 1L;
		}
		return result;
	}
	//第二递推式
	public static long solveB(String in, char[] below, int limit) {
		long result = 0;
		int len = in.length();
		if (len == below.length) {
			//已经填充完毕
			result += solve(in + (char) (((int) below[len - 1] + 1) % 3 + '0'),
					limit);
			result += solve(in + (char) (((int) below[len - 1] + 2) % 3 + '0'),
					limit);
		} else if (len == 0 || below[len - 1] == below[len]) {
			result += solveB(in + (char) (((int) below[len] + 1) % 3 + '0'),
					below, limit);
			result += solveB(in + (char) (((int) below[len] + 2) % 3 + '0'),
					below, limit);
		} else {
			// 0, 1 -> 2
			// 0, 2 -> 1
			// 1, 2 -> 0
			result += solveB(
					in
							+ (char) ((99 - (int) (below[len - 1] + below[len])) % 3 + '0'),
					below, limit);
		}
		return result;
	}
	//i的j次方
	public static int pow(int i, int j) {
		if (j == 0)
			return 1;
		int result = 1;
		for (int k = 0; k < j; k++)
			result = result * i;
		return result;
	}
}
10834893628237824
435ms