NOIP 模拟 玩积木 - 迭代加深搜索 / bfs+hash+玄学剪枝

时间：2024-08-03 08:36:08

题目大意：

有一堆积木，0号节点每次可以和其上方，下方，左上，右下的其中一个交换，问至少需要多少次达到目标状态，若步数超过20，输出too difficult

目标状态：

0

1 1

2 2 2

3 3 3 3

4 4 4 4 4

5 5 5 5 5 5

题目分析：

因为前段时间做了一道转花盆刻骨铭心，所以一看到这题就开始bfs+hash，明知道过不了，但谁知道姿势正确得了85分，后来出题人告诉数据最大步数才14，我把搜索停止条件改成了18，瞬间ac。。。

正解有很多种：迭代加深，双向搜索，\(A^{*}\)……

考后写了一下迭代加深，不是一般的快，具体讲解请百度骑士.

code

bfs + hash + 玄学剪枝

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<string>

#include<algorithm>

#include<cmath>

#include<map>

#include<queue>

using namespace std;

typedef long long ll;

namespace IO{

    inline int read(){

        int i = 0, f = 1; char ch = getchar();

        for(; (ch < '0' || ch > '9') && ch != '-'; ch = getchar());

        if(ch == '-') f = -1, ch = getchar();

        for(; ch >= '0' && ch <= '9'; ch = getchar()) i = (i << 3) + (i << 1) + (ch - '0');

        return i * f;

    }

    inline void wr(ll x){

        if(x < 0) putchar('-'), x = -x;

        if(x > 9) wr(x / 10);

        putchar(x % 10 + '0');

    }

}using namespace IO;

const int N = 10, M = 30;

int T, bin[N], ans;

char initMap[M];

struct node{char s[M]; int cnt;};

queue<node> que; bool flag;

typedef unsigned long long ull;

ull desVal;

const int Mod = 233333, H = 31;

vector<ull> G[Mod + 5];

vector<int> used;

inline bool insert(ull x){

    int key = x % Mod;

    for(int i = 0; i < G[key].size(); i++)

        if(G[key][i] == x) return false;

    G[key].push_back(x); used.push_back(key); return true;

}

inline ull toHash(char s[M]){

    ull ret = 0;

    for(int i = 1; i <= 21; i++) ret = ret * H + s[i] - '0';

    return ret;

}

inline void init(){

    bin[0] = 0;for(int i = 1; i <= 6; i++) bin[i] = bin[i - 1] + i;

    for(int i = 1; i <= 6; i++)

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

            desVal = desVal * H + i - 1;

}

inline pair<int, int> get0Pos(char s[M]){

    pair<int, int> ret;

    for(int i = 1; i <= 6; i++)

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

            if(s[bin[i - 1] + j] == '0') {ret.first = i, ret.second = j; return ret;}

}

inline void add(char s[M], int cnt){

    node tmp;

    for(int i = 1; i <= 21; i++) tmp.s[i] = s[i];

    tmp.cnt = cnt;

    que.push(tmp);

}

int main(){

    T = read(); init();

    while(T--){

        for(int i = 0; i < used.size(); i++) G[used[i]].clear();

        flag = false; ans = 0;

        for(int i = 1; i <= 6; i++)

            for(int j = 1; j <= i; j++) initMap[bin[i - 1] + j] = read() + '0';

        ull hashVal = toHash(initMap);

        if(hashVal == desVal){

            wr(0); putchar('\n');

            continue;

        }

        insert(hashVal);

        while(!que.empty()) que.pop();

        add(initMap, 0);

        while(!que.empty()){

            char now[M];

            node tmp = que.front();

            int cnt = tmp.cnt;

            for(int i = 1; i <= 21; i++) now[i] = tmp.s[i];

            pair<int, int> pos = get0Pos(now);

            //leftup

            if(pos.second != 1){

                swap(now[bin[pos.first - 1] + pos.second], now[bin[pos.first - 1] + pos.second - (bin[pos.first] - bin[pos.first - 1])]);

                ull hashVal = toHash(now);

                if(hashVal == desVal){flag = true, ans = cnt + 1; break;}

                else if(cnt + 1 == 18) break;

                if(insert(hashVal)) add(now, cnt + 1);

                swap(now[bin[pos.first - 1] + pos.second], now[bin[pos.first - 1] + pos.second - (bin[pos.first] - bin[pos.first - 1])]);

            }

            //up

            if(pos.second != bin[pos.first] - bin[pos.first - 1]){

                swap(now[bin[pos.first - 1] + pos.second], now[bin[pos.first - 1] + pos.second - (bin[pos.first] - bin[pos.first - 1]) + 1]);

                ull hashVal = toHash(now);

                if(hashVal == desVal){flag = true, ans = cnt + 1; break;}

                else if(cnt + 1 == 18) break;

                if(insert(hashVal)) add(now, cnt + 1);

                swap(now[bin[pos.first - 1] + pos.second], now[bin[pos.first - 1] + pos.second - (bin[pos.first] - bin[pos.first - 1]) + 1]);

            }

            //down

            if(pos.first != 6){

                swap(now[bin[pos.first - 1] + pos.second], now[bin[pos.first] + pos.second]);

                ull hashVal = toHash(now);

                if(hashVal == desVal){flag = true, ans = cnt + 1; break;}

                else if(cnt + 1 == 18) break;

                if(insert(hashVal)) add(now, cnt + 1);

                swap(now[bin[pos.first - 1] + pos.second], now[bin[pos.first] + pos.second]);

            }

            //rightdown

            if(pos.first != 6){

                swap(now[bin[pos.first - 1] + pos.second], now[bin[pos.first] + pos.second + 1]);

                ull hashVal = toHash(now);

                if(hashVal == desVal){flag = true, ans = cnt + 1; break;}

                else if(cnt + 1 == 18) break;

                if(insert(hashVal)) add(now, cnt + 1);

                swap(now[bin[pos.first - 1] + pos.second], now[bin[pos.first] + pos.second + 1]);

            }

            que.pop();

        }

        if(flag) wr(ans), putchar('\n');

        else printf("too difficult\n");

    }

    return 0;

}

迭代加深

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<string>

#include<algorithm>

#include<cmath>

#include<map>

#include<queue>

using namespace std;

typedef long long ll;

namespace IO{

    inline int read(){

        int i = 0, f = 1; char ch = getchar();

        for(; (ch < '0' || ch > '9') && ch != '-'; ch = getchar());

        if(ch == '-') f = -1, ch = getchar();

        for(; ch >= '0' && ch <= '9'; ch = getchar()) i = (i << 3) + (i << 1) + (ch - '0');

        return i * f;

    }

    inline void wr(ll x){

        if(x < 0) putchar('-'), x = -x;

        if(x > 9) wr(x / 10);

        putchar(x % 10 + '0');

    }

}using namespace IO;

const int N = 10, M = 30;

int T, ans;

int initMap[N][N];

bool flag;

typedef pair<int, int> P;

P pos;

const int des[N][N] = {{0}, {0, 0},{0,1,1},{0,2,2,2},{0,3,3,3,3},{0,4,4,4,4,4},{0,5,5,5,5,5,5}};

inline int H(){

    int ret = -1;

    for(int i = 1; i <= 6; i++)

        for(int j = 1; j <= i; j++) if(initMap[i][j] ^ des[i][j]) ret++;

    return ret;

}

inline bool dfs(int now, int dep, int x, int y){

    if(now > dep){

        if(H() == -1) return true;

        else return false;

    }

    if(H() + now - 1 > dep) return false;

    //leftUp

    if(y != 1){

        swap(initMap[x][y], initMap[x - 1][y - 1]);

        if(dfs(now + 1, dep, x - 1, y - 1)) return true;

        swap(initMap[x][y], initMap[x - 1][y - 1]);

    }

    //up

    if(y != x){

        swap(initMap[x][y], initMap[x - 1][y]);

        if(dfs(now + 1, dep, x - 1, y)) return true;

        swap(initMap[x][y], initMap[x - 1][y]);

    }

    //down

    if(x != 6){

        swap(initMap[x][y], initMap[x + 1][y]);

        if(dfs(now + 1, dep, x + 1, y)) return true;

        swap(initMap[x][y], initMap[x + 1][y]);

    }

    //rightdown

    int tmp = 0;

    for(int i = 1; i < x; i++) tmp += i;

    if(x != 6){

        swap(initMap[x][y], initMap[x + 1][y + 1]);

        if(dfs(now + 1, dep, x + 1, y + 1)) return true;

        swap(initMap[x][y], initMap[x + 1][y + 1]);

    }

    return false;

}

int main(){

    T = read();

    while(T--){

        ans = 0, flag = false;

        for(int i = 1; i <= 6; i++)

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

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

                if(!initMap[i][j]) pos = P(i, j);

            }

        // cout<<pos.first<<" "<<pos.second<<endl;

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

            if(dfs(1, i, pos.first, pos.second)){flag = true, ans = i;break;}

        if(flag) wr(ans), putchar('\n');

        else printf("too difficult\n");

    }

    return 0;

}

相关文章