这里的几个判断是通过下面这个博客，搞懂了轮廓线的定义以及状态转移的：

https://www.cnblogs.com/iiyiyi/p/5846864.html


不过，这个图的轮廓线应该是这样的：

我们当前需要做出来的决策是点（i，j），之前的1代表之前的状态已经确定好（否则是不合法的）

红色线标注出来的是轮廓线，蓝色线标注的是二进制的ID号，是从上到下，从左到右，从大到小标号的

所以，我们当前（i，j）格子有两种方案：

A：不摆~

B：摆，想摆一定是有条件的，同时满足四个条件

条件1：左上角没有摆：左上角存在，且没有摆

条件2：上面没有摆：上面存在，且没有摆

条件3：右上角没有摆：右上角存在，且没有摆

条件4：左面没有摆：左面存在，且没有摆

存在：用（i，j）坐标来判断

是否摆：看当前状态k的对应的二进制位是否为1~~~

（所以，看懂很简单，那为啥不压缩了就挂了。。。）


AC代码：

#include <cstdio>
#include <cstring>
using namespace std;

const int maxn = 10;
int n,K;
long long dp[2][1<<maxn][100],ans;

int getnext(int k){
	if (k & (1<<n))
		k -= 1<<n;
	return k<<1;
}

/*
i:0->n-1
j:0->n-1
*/
bool check(int i,int j,int k){
	if (i&&j&&(k&(1<<n))) return false;//左上角
	// 在第一行或者在第一列或者左上角没有国王
	if (i&&(k&(1<<(n-1)))) return false;//上
	// 在第一行或者上面没有国王
	if (i&&(j<n-1)&&(k&(1<<(n-2)))) return false;//右上角
	//在最后一列或者在第一行或者右上角没有国王
	if (j&&(k&1)) return false;//左边
	// 在第一列或者左边没有国王
	return true;
}

int main(){
	//freopen("input.txt","r",stdin);
	scanf("%d%d",&n,&K);
	int cur=0;
	dp[0][0][0]=1;
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++){
			cur ^= 1;
			memset(dp[cur],0,sizeof(dp[cur]));
			for(int k=0;k<(1<<(n+1));k++)
				for(int t=0;t<=K;t++){
					//int now=getnext(k);
					int now=(k<<1)%(1<<(n+1));
					dp[cur][now][t]+=dp[cur^1][k][t];
					if (t<K&&check(i,j,k)) dp[cur][now+1][t+1]+=dp[cur^1][k][t];
				}
		}
	ans=0;
	for(int k=0;k<(1<<(n+1));k++)
		ans+=dp[cur][k][K];
	printf("%lld\n",ans);
	return 0;
}

改成底下这样就不知道为啥会wa了，很尴尬

#include <cstdio>
#include <cstring>
using namespace std;

const int maxn = 10;
int n,K;
long long dp[maxn][maxn][1<<maxn][100],ans;

int getnext(int k){
	if (k & (1<<n))
		k -= 1<<n;
	return k<<1;
}
/*
i:0->n-1
j:0->n-1
bool check(int i,int j,int k){
	if (i&&j&&(k&(1<<n))) return false;//左上角
	// 在第一行或者在第一列或者左上角没有国王
	if (i&&(k&(1<<(n-1)))) return false;//上
	// 在第一行或者上面没有国王
	if (i&&(j<n-1)&&(k&(1<<(n-2)))) return false;//右上角
	//在最后一列或者在第一行或者右上角没有国王
	if (j&&(k&1)) return false;//左边
	// 在第一列或者左边没有国王
	return true;
}*/

//i:1->n
//j:1->n
bool check(int i,int j,int s){
    if (i>1&&j>1&&(s&(1<<n))) return 0;
    if (i>1&&(s&(1<<n-1))) return 0;
    if (i>1&&j<n&&(s&(1<<n-2))) return 0;
    if (j>1&&(s&1)) return 0;
    return 1;
}

int main(){
	scanf("%d%d",&n,&K);
	memset(dp,0,sizeof(dp));
	dp[0][n][0][0]=1;
	for(int i=1;i<=n;i++){
		for(int j=0;j<(1<<n);j++)
			for(int k=0;k<=K;k++)
				dp[i][0][j<<1][k]=dp[i-1][n][j][k];
		for(int j=1;j<=n;j++)
			for(int k=0;k<(1<<(n+1));k++)
				for(int t=0;t<=K;t++){
					int now=getnext(k);
					//int now=(k<<1)%(1<<(n+1));
					dp[i][j][now][t]+=dp[i][j-1][k][t];
					if (t<K&&check(i,j,k)) dp[i][j][now+1][t+1]+=dp[i][j-1][k][t];
				}
	}
	ans=0;
	for(int k=0;k<(1<<(n+1));k++)
		ans+=dp[n][n][k][K];
	printf("%lld\n",ans);
	return 0;
}