D - Hanjo
2021/5/2 10:27:14
本文主要是介绍D - Hanjo,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
D - Hanjo
原题链接:传送门
分析
数据范围很小我们可以尝试使用暴力枚举
逐行去摆放 主要是考虑对于 2*1 的矩形的两种摆放方式 横着放 1 ,竖着放 2 其余的地方填 3 表示这个位置是1*1 那么对于每一个位置有三种摆放可能 1. 这个位置已经被 2*1 占用 2. 这个位置可以横着放 2 * 1 3. 这个位置可以竖着放 2 * 1 4. 这个位置放 1 * 1
对于搜索类问题我应该考虑什么时候更新答案和什么时候到递归边界
对于这个问题递归的边界就是当坐标 x 超过所给定的矩阵大小。
而更新答案的过程发生在当 A 矩形和 B 矩形都恰好用完。
AC 代码
C++ code
#include <bits/stdc++.h> using namespace std; int h, w, a, b; int m[50][50]; int ans = 0; void dfs(int x, int y, int a, int b) { if(a == 0 && b == 0) { ans ++; return; } if(x > h)return; // 首先获取到当前位置的下一个位置 int nx = x; int ny = y + 1; if(ny > w){ nx ++;ny = 1; } // 1. 检查这个位置是否已经已经被占用 if(m[x][y] > 0) { dfs(nx, ny, a, b); return; // 没有回溯的分支直接接return即可 } // 2. 当前位置直接放 1*1 if(m[x][y] == 0) { m[x][y] = 1; dfs(nx, ny, a, b - 1); m[x][y] = 0; } // 3. 当前位置可以横着放 2 * 1 if(y + 1 <= w && m[x][y] == 0 && m[x][y + 1] == 0) { m[x][y] = m[x][y + 1] = 2; dfs(nx, ny, a - 1, b); m[x][y] = m[x][y + 1] = 0; } if(x + 1 <= h && m[x][y] == 0 && m[x + 1][y] == 0) { m[x+1][y] = m[x][y] = 3; dfs(nx, ny, a - 1, b); m[x+1][y] = m[x][y] = 0; } } int main() { cin >> h >> w >> a >> b; dfs(1, 1, a, b); cout << ans << endl; return 0; }
这篇关于D - Hanjo的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)