别看题目链接,随便放的
【题目描述】
有一个长为$ H $,宽为$ W $的矩形房间。
我们有$ A $个完全一样的$ 2 × 1$的地板和$ B $个完全一样的$ 1 × 1 $的地板。
保证$ 2A + B = HW$。
问有多少种方法用这些地板恰好铺满整个房间。
【输入格式】
一行,四个用空格隔开的整数$H WA B$。
【输出格式】
一行,一个整数表示用这些地板有多少种方法恰好铺满整个房间。
样例输入1
2 2 1 2
样例输出1
4
样例输入2
3 3 4 1
样例输出2
18
简述一下思路
先打一个数组(废话)
然后一行一行的去遍历,如果到了行末就切换到下一行的第一个(就是换行的工作啦)
假如走到了最后一行最后一列(放满了结束了),并且恰好用完地板,$ans++$
下面就是正常操作,在下一个格子内,可以放一个$1*1$的地板
也可以放一个$1*2$的地板,分为竖着放和横着放两种情况
然后正常操作,先赋值为用过,$dfs$,再回溯
小问题:题目既然保证了$ 2A + B = HW $,为什么还要再放一块地板呢?
第一种解释:程序验证一下
第二种解释:逻辑上,不放是没有关系的,但是在程序运行中只会一直放$1*2$的地板,显然是得不到答案的,所以要加上$dfs(x,y + 1,a)$这一行啊
这么水的题目我居然不会写,大意了,学dfs还是基础不牢啊
C++ 代码
#include <bits/stdc++.h>
using namespace std;
int h,w,a,b,ans;
bool used[18][18];
void dfs(int x,int y,int a){
if(y > w) y = 1, x++;
if(x == h && y == w){
if(a == 0) ans++;
return;
}
dfs(x,y + 1,a);
if(a > 0 && used[x][y]){
if(used[x+1][y]){
used[x+1][y] = used[x][y] = false;
dfs(x,y+1,a-1);
used[x+1][y] = used[x][y] = true;
}
if(used[x][y+1]){
used[x][y+1] = used[x][y] = false;
dfs(x,y+1,a-1);
used[x][y+1] = used[x][y] = true;
}
}
}
int main(){
cin >> h >> w >> a >> b;
for(int i = 1;i <= h;i++)
for(int j = 1;j <= w;j++)
used[i][j] = true;
dfs(1,1,a);
cout << ans << endl;
return 0;
}
写完啦
写题解的时候是中午12:00,家长还没到家qwq,然后忍不住一直在写,早饭喝的粥,刚才写的手都软了qwq,吃了一个维C就好多了hhh
谢谢你的阅读,咱们下次见!(主要是该吃午饭了)