Gym-102014E丨最短路丨状压丨Dragon's Cruller

http://codeforces.com/gym/102014/attachments

https://vjudge.net/solution/17440614（题解数据: 264ms/1960kB）

 

题意

给你一个滑块拼图，和一般的不同在于可以从一个边缘跳到另一个边缘。横纵向移动的话费分别位ch，cv。给起始状态和结果状态，求最少花费。

思路

很显然要压缩状态，然后搜索，问题是怎么压怎么搜比较好。

下面这个思路是参考了别人的程序，主要算法是用map和dijkstra双向搜，（因为这样可以节约空间）

数据难以避免地会有漏洞，所以这样搜虽然不一定第一次就取得答案，但是多重复几次（6次）结束就可以了。

是一道蛮好的最短路题~

 

代码

#include<cstdio>
#include<iostream>
#include<vector>
#include<map>
#include<queue>
#include<algorithm>
using namespace std;
typedef long long ll;

const int INF =   0x3F3F3F3F;
const ll Fx9 = 0x00FFFFFFFFF;
const ll Fx1 = 0x0000000000F;
const ll F11 = 0x10000000000;
//用41个数位来表示状态
//前36位里，每4位代表，一个槽上的数
//37~40位表示，0所在槽位号
//41位的0/1表示起点出发或重点出发
//表示好状态以后，用map来记录花费，用dijkstra双向搜
//因为题目数据范围有限，10次以内的交点处就能找到最值。
//所以实际运行的时间没有很大。

int nbrs[9][4] = {
  // R, L, U, D
  {1, 8, 6, 3}, // 0
  {2, 0, 7, 4}, // 1
  {3, 1, 8, 5}, // 2
  {4, 2, 0, 6}, // 3
  {5, 3, 1, 7}, // 4
  {6, 4, 2, 8}, // 5
  {7, 5, 3, 0}, // 6
  {8, 6, 4, 1}, // 7
  {0, 7, 5, 2}, // 8
};
map<ll,int> dis;
struct Less {//重载（）运算符，优先队列
    bool operator()(const ll& a, const ll& b) const {
        return dis[b] < dis[a];
    }
};

ll read() {
    ll bpos = 0,pos = 0;
    ll flds = 0,  d = 0;
    for (int y=0; y < 3; y++)
    for (int x=0; x < 3; x++) {
        scanf("%lld",&d);
        flds |=d<<(pos<<2);
        if(d==0)bpos=pos;
        pos++;
    }
    return (flds|bpos<<36);
}

int main() {
    int ch, cv;
    ll st, gl;

    while(cin>>ch>>cv&&ch+cv){
        st = read();
        gl = read()|F11;

        dis.clear();
        dis[st] = dis[gl] = 0;

        priority_queue<ll,vector<ll>,Less> q;
        q.push(st);
        q.push(gl);
        //双向搜索

        int min_cost = INF;
        int min_check = 6;
        ll u,v;

        while (! q.empty()) {
            u=q.top();
              q.pop();
            v=u^F11;
            if (dis.find(v)!=dis.end()){
                int c=dis[u]+dis[v];
                if (min_cost>c) min_cost = c;
                if (--min_check<=0)break;
            }
            ll upos = (u>>36) & Fx1;
            for (int i = 0; i < 4; i++) {
                ll vpos = nbrs[upos][i];
                int nvd = dis[u] + (i<2?ch:cv);
                ll k =(u >>(vpos*4))& Fx1;
                ll v =(u &(Fx9|F11) & ~(Fx1<<(vpos*4)))|(k<<(upos*4))|(vpos<<36);

                if (dis.find(v) == dis.end())
                    dis[v] = nvd,q.push(v);
                else if (dis[v] > nvd)
                    dis[v] = nvd;
            }
        }
        cout << min_cost << endl;
    }

  return 0;
}
/*
4 9
6 3 0
8 1 2
4 5 7
6 3 0
8 1 2
4 5 7
31 31
4 3 6
0 1 5
8 2 7
0 3 6
4 1 5
8 2 7
92 4
1 5 3
4 0 7
8 2 6
1 5 0
4 7 3
8 2 6
12 28
3 4 5
0 2 6
7 1 8
5 7 1
8 6 2
0 3 4
0 0
*/