[AcWing 179] 八数码
2022/8/7 23:23:47
本文主要是介绍[AcWing 179] 八数码,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
A* 算法
点击查看代码
#include<bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<int,string> PIS; const int N = 1e6 + 10; string start; int dx[] = {-1, 0, 1, 0}; int dy[] = {0, 1, 0, -1}; char op[] = {'u', 'r', 'd', 'l'}; int f(string s) { int res = 0; for (int i = 0; i < s.size(); i ++) if (s[i] != 'x') { int t = s[i] - '1'; res += abs(i / 3 - t / 3) + abs(i % 3 - t % 3); } return res; } string bfs() { string end = "12345678x"; unordered_map<string, int> d; unordered_map<string, pair<string,char>> pre; priority_queue<PIS, vector<PIS>, greater<PIS>> heap; heap.push({f(start), start}); d[start] = 0; while (heap.size()) { auto t = heap.top(); heap.pop(); string s = t.second; if (s == end) break; int step = d[s]; int p = s.find('x'); int x = p / 3, y = p % 3; string pre_s = s; for (int i = 0; i < 4; i ++) { int a = x + dx[i], b = y + dy[i]; if (a < 0 || a >= 3 || b < 0 || b >= 3) continue; swap(s[x * 3 + y], s[a * 3 + b]); if (!d.count(s) || d[s] > step + 1) { d[s] = step + 1; pre[s] = {pre_s, op[i]}; heap.push({d[s] + f(s), s}); } swap(s[x * 3 + y], s[a * 3 + b]); } } string res; while (end != start) { res += pre[end].second; end = pre[end].first; } reverse(res.begin(), res.end()); return res; } void solve() { char c; while (cin >> c) { start += c; } int t = 0; for (int i = 0; i < start.size(); i ++) for (int j = i + 1; j < start.size(); j ++) { int s1 = start[i], s2 = start[j]; if (s1 == 'x' || s2 == 'x') continue; if (s1 > s2) t ++; } if (t % 2) cout << "unsolvable" << endl; else cout << bfs() << endl; } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); solve(); return 0; }
- 八数码问题
设 \(s\) 为输入字符串去掉 \(x\) 后的字符串
① 当 \(s\) 的逆序对个数为奇数时,无解
② 当 \(s\) 的逆序对个数为偶数时,有解 - 估价函数
\(1\) ~ \(8\) 每个数和最终位置的曼哈顿距离之和,这个距离之和小于真实的移动次数,满足 \(A^{*}\) 算法估价值小于真实值的条件 - 在原来八数码问题的基础上,用 \(A^{*}\) 算法缩小搜索范围,并且记录方案
这篇关于[AcWing 179] 八数码的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升
- 2024-05-08代码报错不用愁,CodeGeeX一键完成代码修复、错误解释的功能上线了!
- 2024-05-08今天开始程序员不用再发愁写commit message了,全部由CodeGeeX自动完成!