{
if(g_Width == 0 && g_Height == 0)
{
break;
}
if(g_Width > g_Height)
{
swap(g_Width, g_Height);
}
int nAllStatus = 2 << (g_Width-1);
memset(DP, 0, sizeof(DP));
for( j = 0; j < nAllStatus; j++)
{
if(TestFirstLine(j))
{
DP[0][j] = 1;
}
}
for( i = 1; i < g_Height; i++)
{
for( j = 0; j < nAllStatus; j++)// iterate all status for line i
{
for( k = 0; k < nAllStatus; k++) // iterate all status for line i-1
{
if(CompatablityTest(j, k))
{
DP[i][j] += DP[i-1][k];
}
}
}
}
printf("%lld\n", DP[g_Height-1][nAllStatus - 1]);
}
return 0;
}
几点注意：因为算法 复杂度是 H * (W^4) 所以当 W > H的时候，我们交换他们这样适当降低复杂度。
另外数据到后面比较大，所以使用 long long( __int64)
作者：hopeztm