算法1(DFS) 只过10个测试点 但是思路比较简单
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N=110,M=110;
const int Mod=1000000007;
int n,m,k;
int xx[8] = {-2,-1,1,2,2,1,-1,-2};
int yy[8] = {1,2,2,1,-1,-2,-2,-1};
int g[N][M];
int res;
void dfs(int x,int y,int num){
if(num==k){
res=(res+1)%Mod;
return;
}
if(y>m){
y=1,x++;
if(x>n)return;
}
dfs(x,y+1,num);//(x,y)不放
if(!g[x][y]){//如果(x,y)可以放马,就放马
//更新一下状态(在(x,y)处放马后,哪些位置不能放马了)
g[x][y]++;
for(int i=0;i<8;i++){
int dx=x+xx[i],dy=y+yy[i];
if(dx<=n&&dy<=m&&dx>=1&&dy>=1)g[dx][dy]++;
}
dfs(x,y+1,num+1);//放马后,马的数量num+1
//恢复
g[x][y]--;
for(int i=0;i<8;i++){
int dx=x+xx[i],dy=y+yy[i];
if(dx<=n&&dy<=m&&dx>=1&&dy>=1)g[dx][dy]--;
}
}
}
int main(){
cin>>n>>m>>k;
dfs(1,1,0);
cout<<res;
return 0;
}
算法2 (状态压缩DP)
i-2列状态为c
i-1列状态为a
i列状态为b
f[i,a,b,k]:表示已经放好了前i-1行,第i-1的状态是a,第i行的状态是b,共放了k个马的方案的集合
理论上时间为100*64*64*20*64≈5亿
但是中间有跳出的条件 所有最后能过
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N=110,K=21,M=1<<6;
const int Mod=1000000007;
int n,m,k;
int f[N][M][M][K];
//f[i,a,b,k]:表示已经放好了前i-1行,第i-1的状态是a,第i行的状态是b,共放了k个马的方案的集合
int h[M]; //h[state]表示状态state中1的个数
int get_count(int state){
int res=0;
while(state){
if(state&1)res++;
state=state>>1;
}
return res;
}
int main(){
cin>>n>>m>>k;
f[0][0][0][0]=1;
for(int i=1;i<(1<<n);i++){
h[i]=get_count(i);
}
for(int i=1;i<=m;i++){
for(int a=0;a<(1<<n);a++){ //i-1列
for(int b=0;b<(1<<n);b++){//i列
if((a&(b<<2))||(b&(a<<2)))continue;
for(int c=0;c<(1<<n);c++){ //i-2列
if((c&(b<<1))||(b&(c<<1)))continue;
if((c&(a<<2))||(a&(c<<2)))continue;
int t=h[b];//第i列中1的个数
for(int j=t;j<=k;j++)
f[i][a][b][j]=(f[i][a][b][j]+f[i-1][c][a][j-t])%Mod;
}
}
}
}
int res=0;
for(int a=0;a<(1<<n);a++)
for(int b=0;b<(1<<n);b++)
res=(res+f[m][a][b][k])%Mod;
cout<<res;
return 0;
}