首页 > 代码库 > UVALive 6665 Dragonas Cruller
UVALive 6665 Dragonas Cruller
题目链接:https://icpcarchive.ecs.baylor.edu/external/66/6665.pdf
题目大意:
有一个3 * 3 的格子:
每一个格子上面的数字可以朝上下左右四个方向移动,如果移出范围,则到与其边界上字母对应的另一边。如下图所示:
空白部分分别向上下左右移动之后的情况。
现在,给你左右移动的费用ch,上下移动cv。给你一个初始状态(9个数字,其中0代表该空格为空),一个结束状态,问从初始状态移动到结束状态的最小花费。
解题思路:
其实这道题想法很简单,简单的bfs + 优先队列。主要是细节处理方面比较麻烦。
把上述九宫格变为一个序列,会发现状态最多就9!种,所以状态可以按照序列的排序离散化。具体参考代码。
然后改成序列之后,会发现左右移动其实就是 i + 1, i - 1的操作,上下移动是 i + 3, i - 3 的操作。
代码:
#include<map> #include<set> #include<queue> #include<stack> #include<cmath> #include<cstdio> #include<vector> #include<string> #include<fstream> #include<cstring> #include<ctype.h> #include<iostream> #include<algorithm> #define maxn 1000 #define INF (1<<30) #define PI acos(-1.0) #define mem(a, b) memset(a, b, sizeof(a)) #define For(i, n) for (int i = 0; i < n; i++) #define debug puts("===============") const int N = 362881; typedef long long ll; using namespace std; int ch, cv; int fac[10]; struct node { int x, w; node(int _x, int _w) { x = _x, w = _w; } bool operator < (const node & T) const { return w > T.w; } }; void Atoint(int* a, int &x) { int i, j, y; x = 0; for (i = 0; i < 9; i++) { y = a[i]; for (j = 0; j < i; j++) if (a[j] < a[i]) y--; x += fac[8 - i] * y; } } void inttoA(int x, int* a) { int has[10] = {0}; int i, j, y; for (i = 0; i < 9; i++) { y = x / fac[8 - i]; for (j = 0; j < 9; j++) if (!has[j]) { if (y == 0) break; y--; } a[i] = j, has[j] = 1, x %= fac[8 - i]; } } int st, ed; priority_queue<node> q; int d[N], vis[N], a[10], b[10]; void update(int x, int w) { if (!vis[x] && d[x] > w) { d[x] = w, q.push(node(x, w)); } } void work() { Atoint(a, st), Atoint(b, ed); while(!q.empty()) q.pop(); memset(d, 0x7F, sizeof(d)); memset(vis, 0, sizeof(vis)); d[st] = 0; q.push(node(st, 0)); int x, w, i, y; while(!q.empty()) { x = q.top().x, w = q.top().w, q.pop(); if (vis[x]) continue; vis[x] = 1; if (x == ed) { printf("%d\n", w); break; } inttoA(x, a); for (i = 0; i < 9; i++) if (!a[i]) break; swap(a[i], a[(i + 1) % 9]); Atoint(a, y); update(y, w + ch); swap(a[i], a[(i + 1) % 9]); swap(a[i], a[(i + 8) % 9]); Atoint(a, y); update(y, w + ch); swap(a[i], a[(i + 8) % 9]); swap(a[i], a[(i + 3) % 9]); Atoint(a, y); update(y, w + cv); swap(a[i], a[(i + 3) % 9]); swap(a[i], a[(i + 6) % 9]); Atoint(a, y); update(y, w + cv); } } int main () { //freopen("1.txt", "r", stdin); fac[0] = 1; for (int i = 1; i < 10; i++) fac[i] = fac[i - 1] * i; while(scanf("%d%d", &ch, &cv), ch || cv) { for (int i = 0; i < 9; i++) scanf("%d", a + i); for (int i = 0; i < 9; i++) scanf("%d", b + i); work(); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。