链接:https://ac.nowcoder.com/acm/contest/301/B
来源:牛客网
题目描述
小乐乐想要给自己搭建一个积木城堡。
积木城堡我们假设为n*m的平面矩形。
小乐乐现在手里有1*2,2*1两种地砖。
小乐乐想知道自己有多少种组合方案。
输入描述:
第一行输入整数n,m。(1<=n,m<=10)
输出描述:
输出组合方案数。
示例1
输入
2 3
输出
3
说明
示例2
输入
1 3
输出
0
示例3
输入
2 5
输出
8
题意:略
题解:想象成竖着的平面矩形,然后详细看代码;
#include <iostream>
#include <cstring>
using namespace std;
const int MAX = 20;
bool vis[MAX][MAX];
int mv[2][2]={0,1,1,0};//加的木块只有在原木块的上面或者右面;
int ans,n,m;//n是宽m是长
void dfs(int area){
if(area==n*m){
ans++;
return;
}
int x=area/n;
int y=area%n;
if(vis[x][y]) return dfs(area+1);//因为是 2*1 1*2的木块
vis[x][y]=true;
for (int i = 0; i < 2;i++){
int xx=x+mv[i][0];
int yy=y+mv[i][1];
if(xx<m&&yy<n&&!vis[xx][yy]){
vis[xx][yy]=1;
dfs(area+1);
vis[xx][yy]=0;
}
}
vis[x][y]=0;
return;
}
int main(){
cin >> n >> m;
if((n*m)&1){
cout << 0 << endl;
return 0;
}
dfs(0);
cout << ans << endl;
//memset(vis,0,sizeof(vis));
// ans=0;
return 0;
}