题意

中文题意

思路

做这题的前置技能学习

康托展开

这个东西我认为就是在排列组合问题上的Hash算法，可以压缩空间。
A*搜索。

这里我使用了像k短路一样的做法，从最终状态倒回去预处理一遍距离，但是跑了0.8s，可能是预处理花费的时间太多了。有些人用曼哈顿距离估价，跑了0.2s。

#include <bits/stdc++.h>

using namespace std;

const int INF = 0x3f3f3f3f;

const int N = 1e5 + 10;

typedef long long LL;

struct Node {

    int x, y, f, g, kt, mm[4][4];

    bool operator < (const Node &rhs) const {

        return f > rhs.f;

    }

};

int init[4][4] = {

    { 1, 2, 3 },

    { 4, 5, 6 },

    { 7, 8, 0 }

};

int mp[4][4], ans, h[500001], vis[500001], target;

int f[10], dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};

int kangtuo(int mp[4][4]) {

    int sum = 0;

    for(int i = 0; i < 9; i++) {

        int now = 0;

        for(int j = i + 1; j < 9; j++) {

            if(mp[i/3][i%3] > mp[j/3][j%3]) now++;

        }

        sum += now * f[9-i-1];

    } return sum + 1;

}

void BFS(int x, int y) {

    memset(h, INF, sizeof(h));

    queue<Node> que;

    Node now = (Node) {x, y, 0, 0};

    for(int i = 0; i < 3; i++) for(int j = 0; j < 3; j++)

        now.mm[i][j] = init[i][j];

    h[target] = 0;

    que.push(now);

    while(!que.empty()) {

        Node now = que.front(); que.pop();

        int x = now.x, y = now.y, f = now.f;

        for(int i = 0; i < 4; i++) {

            now.x = x + dx[i], now.y = y + dy[i];

            if(now.x < 0 || now.x > 2 || now.y < 0 || now.y > 2) continue;

            swap(now.mm[x][y], now.mm[now.x][now.y]);

            int nf = f + 1, nkt = kangtuo(now.mm);

            now.f = nf;

            if(h[nkt] == INF) {

                h[nkt] = nf;

                que.push(now);

            }

            swap(now.mm[x][y], now.mm[now.x][now.y]);

        }

    }

}

void YCL() {

    BFS(2, 2);

}

int Astar(int x, int y) {

    priority_queue<Node> que;

    memset(vis, 0, sizeof(vis));

    vis[kangtuo(mp)] = 1;

    Node now = (Node) { x, y, 0, 0, kangtuo(mp)};

    for(int i = 0; i < 3; i++)

        for(int j = 0; j < 3; j++)

            now.mm[i][j] = mp[i][j];

    que.push(now);

    while(!que.empty()) {

        now = que.top(); que.pop();

        int x = now.x, y = now.y, f = now.f, g = now.g, kt = now.kt;

        if(kt == target) return f;

        for(int i = 0; i < 4; i++) {

            int nx = x + dx[i], ny = y + dy[i];

            if(nx < 0 || nx > 2 || ny < 0 || ny > 2) continue;

            swap(now.mm[x][y], now.mm[nx][ny]);

            int nkt = kangtuo(now.mm);

            now.x = nx, now.y = ny, now.g = g + 1, now.f = now.g + h[nkt], now.kt = nkt;

            if(!vis[nkt]) {

                vis[nkt] = 1;

                que.push(now);

            }

            swap(now.mm[x][y], now.mm[nx][ny]);

        }

    } return -1;

}

int main() {

    f[0] = 1;

    for(int i = 1; i < 9; i++) f[i] = f[i-1] * (i);

    target = kangtuo(init);

    YCL();

    int t; scanf("%d", &t);

    while(t--) {

        int ix, iy;

        for(int i = 0; i < 3; i++)

            for(int j = 0; j < 3; j++) {

                scanf("%d", &mp[i][j]);

                if(mp[i][j] == 0) ix = i, iy = j;

            }

        ans = Astar(ix, iy);

        if(~ans) printf("%d\n", ans);

        else puts("No Solution!");

    }

    return 0;

}

巴特西

hihoCoder 1312：搜索三·启发式搜索（A* + 康托展开）

题意

思路

最新文章

热门文章