題目鏈接: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; }