POJ - 1084 Square Destroyer(IDA*算法)
2022/1/18 14:06:25
本文主要是介绍POJ - 1084 Square Destroyer(IDA*算法),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
POJ - 1084 Square Destroyer
#include <cstdio> #include <cstring> #include <vector> using namespace std; const int N = 61; // 网格最大是 5 * 5 的,其中最多会有 5 * (5 + 1) * 2 = 60 个正方形,所以要开到 61 int n, idx; // n 为网格规模,idx 为正方形数量 int max_depth; // IDA* 的 max_depth vector<int> square[N]; // 存每个正方形边上的火柴的编号 bool used[N]; // 存每个火柴是否已经被破坏 // 新加一个左上角坐标为 (r, c),边长为 len 的正方形 void add(int r, int c, int len) { int d = n << 1 | 1; // 由于用到的 2n + 1 比较多,这里先用一个变量代替掉 2n + 1 vector<int> &s = square[idx]; s.clear(); // 有多组测试数据,需要上一组数据的内容清空 for (int i = 0; i < len; i ++ ) { s.push_back(1 + r * d + c + i); // 上边第 i 个 s.push_back(1 + (r + len) * d + c + i); // 下边第 i 个 s.push_back(1 + n + r * d + c + i * d); // 左边第 i 个 s.push_back(1 + n + r * d + c + i * d + len); // 右边第 i 个 } idx ++ ; } // 判断正方形 s 是否完整 bool check(vector<int> &s) { for (int i = 0; i < (int)s.size(); i ++ ) if (used[s[i]]) return false; // 如果其中有一条边已经被破坏了,那么说明不完整 return true; // 如果每条边都没被破坏,说明完整 } // 估价函数 int f() { static bool backup[N]; // 由于要改动 used,需要先新建一个备份数组 memcpy(backup, used, sizeof used); // 将 used 复制到备份数组中 int res = 0; for (int i = 0; i < idx; i ++ ) // 枚举所有正方形 if (check(square[i])) // 如果某个正方形是完整的, { res ++ ; // 那么 res ++ ,并将该正方形所有的边都删去 for (int j = 0; j < (int)square[i].size(); j ++ ) used[square[i][j]] = true; } memcpy(used, backup, sizeof used); // 复制回来 return res; } // IDA* bool dfs(int depth) { if (depth + f() > max_depth) return false; for (int i = 0; i < idx; i ++ ) // 枚举所有的正方形 if (check(square[i])) // 如果第 i 个正方形还没被破坏 {// 那么枚举该正方形的所有边编号,去掉该边并继续爆搜 for (int j = 0; j < (int)square[i].size(); j ++ ) { used[square[i][j]] = true; if (dfs(depth + 1)) return true; used[square[i][j]] = false; } return false;// 如果每条边都爆搜不成功,那么说明删掉 max_depth 个火柴无法破坏该正方形 } return true; // 如果所有的正方形都被破坏了,返回 true } int main() { int T;scanf("%d",&T); while (T -- ) { scanf("%d", &n), idx = 0; // 初始化 idx memset(used, false, sizeof used); // 初始化 used for (int len = 1; len <= n; len ++ ) // 枚举 len, r, c,预处理每个正方形 for (int r = 0; r + len <= n; r ++ ) for (int c = 0; c + len <= n; c ++ ) add(r, c, len); int k;scanf("%d", &k); while (k -- ) // 读入所有已经被破坏的边 { int x;scanf("%d", &x); used[x] = true; } max_depth = 0; // IDA* while (!dfs(0)) max_depth ++ ; printf("%d\n", max_depth); } return 0; }
这篇关于POJ - 1084 Square Destroyer(IDA*算法)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-02springboot项目无法注册到nacos-icode9专业技术文章分享
- 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题)