暴力求解和IDA*(三)

状态空间搜索会遇到一些比较复杂的算法
需要构建中间状态的转换，有时候算法实现会比较复杂

记一次快让我疯掉的优化经历

这道题目的数据很强，对时间复杂度和空间复杂度要求都非常高

一开始想用bfs做

先用朴素的bfs加上Hash计算出正确的答案
和普通的八数码问题相比，就多了一些中间状态的转移

//
//  main.cpp
//  POJ3131
//
//  Created by zhangmin chen on 2019/7/15.
//  Copyright © 2019 zhangmin chen. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <bitset>
#include <assert.h>

using namespace std;
typedef long long llong;
typedef set<int>::iterator ssii;

const int N = 3;
const int maxstate = 5000000;
const int hashSZ = 5000003;

#define Cmp(a, b) memcmp(a, b, sizeof(b))
#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define Set(a, v) memset(a, v, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define _forS(i, l, r) for(set<int>::iterator i = (l); i != (r); i++)
#define _rep(i, l, r) for(int i = (l); i <= (r); i++)
#define _for(i, l, r) for(int i = (l); i < (r); i++)
#define _forDown(i, l, r) for(int i = (l); i >= r; i--)
#define debug_(ch, i) printf(#ch"[%d]: %d\n", i, ch[i])
#define debug_m(mp, p) printf(#mp"[%d]: %d\n", p->first, p->second)
#define debugS(str) cout << "dbg: " << str << endl;
#define debugArr(arr, x, y) _for(i, 0, x) { _for(j, 0, y) printf("%c", arr[i][j]); printf("\n"); }
#define _forPlus(i, l, d, r) for(int i = (l); i + d < (r); i++)

const string CH = "WRBE";
// const int BUFLEN = 4;
const int W = 0, R = 1, B = 2, E = 3;

const int DICE[3][3] = {
    {-1, B, R},
    {B, -1, W},
    {R, W, -1},
};

const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, -1, 0, 1};
const int UP = 0, LEFT = 1, DOWN = 2, RIGHT = 3;
// usage: dx[LEFT], dy[LEFT]

//const int revDir[] = {DOWN, RIGHT, UP, LEFT};
//const string DIR[] = {"UP", "LEFT", "DOWN", "RIGHT"};
// usage: revD = revDir[LEFT]

class CUBE {
public:
    int top, face, bottom, back, left, right;
    // set DICE[top][face] = LEFT;
    void clear() {
        top = face = bottom = back = left = right = 0;
    }
    
    bool operator!= (const CUBE& rhs) const {
        return top != rhs.top || face != rhs.face || left != rhs.left;
    }
};

typedef CUBE State[N][N];
int dist[maxstate];
State nodes[maxstate];
int head[hashSZ], nxth[maxstate];

void initHash() {
    Set(head, 0);
    Set(nxth, 0);
    Set(dist, 0);
    _for(k, 0, maxstate) {
        _for(i, 0, N) _for(j, 0, N) nodes[k][i][j].clear();
    }
}

void setPos(CUBE& cb, int _top, int _face) {
    //assert(cb.top != E);
    cb.top = _top;
    cb.face = _face;
    cb.left = DICE[_top][_face];
    
    cb.right = cb.left;
    cb.bottom = cb.top;
    cb.back = cb.face;
}

void setEmpty(CUBE& cb) {
    cb.top = cb.bottom = cb.left = cb.right = cb.face = cb.back = E;
}

CUBE Move(const CUBE& cb, int dir) {
    CUBE nxt;
    if(dir == UP) setPos(nxt, cb.face, cb.bottom);
    if(dir == DOWN) setPos(nxt, cb.back, cb.top);
    if(dir == LEFT) setPos(nxt, cb.right, cb.face);
    if(dir == RIGHT) setPos(nxt, cb.left, cb.face);
    
    return nxt;
}

int _hash(const State& st) {
    int val = 0;
    _for(i, 0, N) _for(j, 0, N) {
        val = val * 10 + st[i][j].top;
    }
    return val % hashSZ;
}

// h is hash value
void link(int id, int h) {
    nxth[id] = head[h];
    head[h] = id;
}

int cmpr(State& s1, State& s2) {
    _for(i, 0, N) _for(j, 0, N) {
        if(s1[i][j] != s2[i][j]) return 1;
    }
    return 0;
}

bool tryInsert(int id) {
    int h = _hash(nodes[id]);
    // debug(h);
    int u = head[h];
    
    while (u) {
        //
        if(cmpr(nodes[id], nodes[u]) == 0) return 0;
        u = nxth[u];
    }
    link(id, h);
    return true;
}

bool inRange(int x, int l, int r) {
    if(l > r) return inRange(x, r, l);
    return l <= x && x <= r;
}

bool valid(int x, int y) {
    return inRange(x, 0, 2) && inRange(y, 0, 2);
}

CUBE pan[N][N];

void initPan() {
    _for(i, 0, N) _for(j, 0, N) {
        CUBE cur;
        // cur.setPos(W, R);
        setPos(cur, W, R);
        pan[i][j] = cur;
    }
}

char target[N][N];
void initTar() {
    Set(target, 0);
}

void dbgPan(const CUBE pan[][N]) {
    _for(i, 0, N) {
        _for(j, 0, N) printf("%c ", CH[pan[i][j].top]);
        printf("\n");
    }
    printf("\n");
}

void dbgTar() {
    _for(i, 0, N) {
        _for(j, 0, N) printf("%c ", target[i][j]);
        printf("\n");
    }
    printf("\n");
}

void findEmpty(const CUBE pan[][N], int& ex, int& ey) {
    _for(i, 0, N) _for(j, 0, N) {
        const CUBE& cur = pan[i][j];
        if(CH[cur.top] == 'E') {
            ex = i;
            ey = j;
            return;
        }
    }
    return;
}

bool reach(const CUBE pan[][N], const char target[][N]) {
    //
    _for(i, 0, N) _for(j, 0, N) {
        //
        if(CH[pan[i][j].top] != target[i][j]) return 0;
    }
    return 1;
}

void assign(const CUBE pan[][N], State* nodes, int id) {
    _for(i, 0, N) _for(j, 0, N) {
        nodes[id][i][j] = pan[i][j];
    }
}


int bfs() {
    int front = 1, rear = 2;
    
    while (front < rear) {
        State& cur = nodes[front];
        if(reach(cur, target)) return front;
        
        int ex = -1, ey = -1;
        findEmpty(cur, ex, ey);
        assert(ex != -1 && ey != -1);
        
        _for(dir, 0, 4) {
            int nx = ex + dx[dir], ny = ey + dy[dir];
            if(!valid(nx, ny)) continue;
            
            State& to = nodes[rear];
            Cpy(to, cur);
            
            CUBE nxt = Move(cur[nx][ny], dir);
            to[nx][ny] = cur[ex][ey];
            to[ex][ey] = nxt;
            // dbgPan(to);
            
            dist[rear] = dist[front] + 1;
            if(tryInsert(rear)) rear++;
        }
        front++;
    }
    return 0;
}


// ans init as inf
// eCb is empty cube

// remember the parent of empty block



int main() {
    freopen("input.txt", "r", stdin);
    int ex, ey;
    int kase = 1;
    while (scanf("%d%d", &ex, &ey) == 2 && ex && ey) {
        initHash();
        initPan();
        initTar();
        
        setEmpty(pan[ey - 1][ex -1]);
        assign(pan, nodes, 1);
        
        _for(i, 0, N) _for(j, 0, N) {
            cin >> target[i][j];
        }
        
        printf("Case: %d\n", kase++);
        // input finished()
        
        //dbgPan(nodes[1]);
        // dbgTar();
        
        int ans = bfs();
        if(dist[ans] <= 30) printf("%d\n", dist[ans]);
        else printf("-1\n");
        // cout << "========" << endl;
        
    }
}

和朴素八数码问题比，就多了中间状态的转换
用 $\text{Move}[\cdots]$ 数组来表示

但是时间复杂度非常之高
并且耗内存，但是可以得到正确的结论

接下来进行优化

状态压缩编码和双向bfs优化

用这种优化方法，是可以通过
LA3618
LA3618的数据并不是很强

具体的思路如下：
终点状态已知top面的颜色，每一个top面对应的face面有2种可能
每个位有2种编码，一共有
$2^{8}=256$ 种编码方式
用解答树填空法，把终点状态入队列que2

起点状态只有一种编码，也入队列

POJ3131
POJ3131-2
POJ3131-3

算法实现

//
//  main.cpp
//  POJ3131-2
//
//  Created by zhangmin chen on 2019/7/19.
//  Copyright © 2019 zhangmin chen. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <bitset>
#include <assert.h>

using namespace std;
typedef long long llong;
typedef set<int>::iterator ssii;


#define Cmp(a, b) memcmp(a, b, sizeof(b))
#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define Set(a, v) memset(a, v, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define _forS(i, l, r) for(set<int>::iterator i = (l); i != (r); i++)
#define _rep(i, l, r) for(int i = (l); i <= (r); i++)
#define _for(i, l, r) for(int i = (l); i < (r); i++)
#define _forDown(i, l, r) for(int i = (l); i >= r; i--)
#define debug_(ch, i) printf(#ch"[%d]: %d\n", i, ch[i])
#define debug_m(mp, p) printf(#mp"[%d]: %d\n", p->first, p->second)
#define debugS(str) cout << "dbg: " << str << endl;
#define debugArr(arr, x, y) _for(i, 0, x) { _for(j, 0, y) printf("%c", arr[i][j]); printf("\n"); }
#define _forPlus(i, l, d, r) for(int i = (l); i + d < (r); i++)

const int BASE[] = {1, 6, 36, 216, 1296, 7776, 46656, 279936, 1679616};
const int maxn = 1679616 + 10;

class Node {
public:
    int st[9];
    int ep, dta, dist;
};

queue<Node> que1, que2;
Node s1, s2;

bool vis1[maxn][9];
bool vis2[maxn][9];
char tar[9];

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

void initVis() {
    Set(vis1, 0);
    Set(vis2, 0);
}

void initQue() {
    while(!que1.empty()) que1.pop();
    while(!que2.empty()) que2.pop();
}

/*
 if(top == W && face == R) return 0;
 if(top == W && face == B) return 1;
 if(top == R && face == W) return 2;
 if(top == R && face == B) return 3;
 if(top == B && face == W) return 4;
 if(top == B && face == R) return 5;
 return -1;
 
 */

// const int Move[0][dir]
// const int Move[1][dir]
// UP LEFT DOWN RIGHT
// Move[0][UP] = (R, W)  Move[0][LEFT] = (B, R) Move[0][DOWN] = (R, W)  Move[0][RIGHT] = (B, R)
// Move[1][UP] = (B, W)  Move[1][LEFT] = (R, B)
// Move[2][UP] = (W, R)  Move[2][LEFT] = (B, W)
// Move[3][UP] = (B, R)  Move[3][LEFT] = (W, B)
// Move[4][UP] = (W, B)  Move[4][LEFT] = (R, W)
// Move[5][UP] = (R, B)  Move[5][LEFT] = (W, R)

const int Move[6][4] = {
    {2, 5, 2, 5},
    {4, 3, 4, 3},
    {0, 4, 0, 4},
    {5, 1, 5, 1},
    {1, 2, 1, 2},
    {3, 0, 3, 0}
};
// usage: int newCode = Move[oldCode][dir]

int cal(const Node x) {
    int k = 0, ans = 0;
    _for(i, 0, 9) {
        if(i != x.ep) ans = ans + x.st[i] * BASE[k++];
    }
    return ans;
}

bool valid(int x, int y) {
    if(0 <= x && x < 3 && 0 <= y && y < 3) return 1;
    return 0;
}

void dfs(Node& s2, int d) {
    if(d == 9) {
        s2.dist = 0;
        s2.dta = cal(s2);
        que2.push(s2);
        vis2[s2.dta][s2.ep] = true;
        return;
    }
    
    if(tar[d] == 'W') {
        s2.st[d] = 0;
        dfs(s2, d + 1);
        
        s2.st[d] = 1;
        dfs(s2, d + 1);
    }
    else if(tar[d] == 'R') {
        s2.st[d] = 2;
        dfs(s2, d + 1);
        
        s2.st[d] = 3;
        dfs(s2, d + 1);
    }
    else if(tar[d] == 'B') {
        s2.st[d] = 4;
        dfs(s2, d + 1);
        
        s2.st[d] = 5;
        dfs(s2, d + 1);
    }
    else {
        s2.st[d] = 6;
        dfs(s2, d + 1);
    }
}

bool bfs(int& ans) {
    const int DEP1 = 21, DEP2 = 9;
    int cnt1 = 0, cnt2 = 0, flag = 0;
    
    while (true) {
        flag = 0;
        
        while (!que1.empty() && que1.front().dist <= cnt1) {
            flag = 1;
            //
            Node x = que1.front(); que1.pop();
            if(vis2[x.dta][x.ep]) {
                ans = x.dist + cnt2;
                return true;
            }
            
            if(x.dist >= DEP1) continue;
            
            _for(dir, 0, 4) {
                Node nxt = x;
                int ex = x.ep / 3, ey = x.ep % 3;
                int nx = ex + dx[dir], ny = ey + dy[dir];
                
                if(!valid(nx, ny)) continue;
                
                int np = nx * 3 + ny;
                nxt.ep = np;
                
                nxt.st[x.ep] = Move[nxt.st[nxt.ep]][dir];
                nxt.st[nxt.ep] = 6;
                
                nxt.dist = x.dist + 1;
                nxt.dta = cal(nxt);
                
                if(!vis1[nxt.dta][nxt.ep]) {
                    vis1[nxt.dta][nxt.ep] = true;
                    que1.push(nxt);
                }
            }
        }
        if(cnt1 < DEP1) cnt1++;
        
        while (!que2.empty() && que2.front().dist <= cnt2) {
            flag = 1;
            //
            Node x = que2.front(); que2.pop();
            if(vis1[x.dta][x.ep]) {
                ans = x.dist + cnt1;
                return true;
            }
            
            if(x.dist >= DEP2) continue;
            
            _for(dir, 0, 4) {
                Node nxt = x;
                int ex = x.ep / 3, ey = x.ep % 3;
                int nx = ex + dx[dir], ny = ey + dy[dir];
                
                if(!valid(nx, ny)) continue;
                
                int np = nx * 3 + ny;
                nxt.ep = np;
                
                nxt.st[x.ep] = Move[nxt.st[nxt.ep]][dir];
                nxt.st[nxt.ep] = 6;
                
                nxt.dist = x.dist + 1;
                nxt.dta = cal(nxt);
                
                if(!vis2[nxt.dta][nxt.ep]) {
                    vis2[nxt.dta][nxt.ep] = true;
                    que2.push(nxt);
                }
            }
        }
        if(cnt2 < DEP2) cnt2++;
        if(!flag) return false;
    }
}


int main() {
    freopen("input.txt", "r", stdin);
    
    int ex, ey;
    while (scanf("%d%d", &ex, &ey) != EOF && ex && ey) {
        initVis();
        ex--; ey--;
        int ep = ey * 3 + ex;
        
        initQue();
        
        // get bfs s1
        _for(i, 0, 9) {
            if(i == ep) {
                //
                s1.st[i] = 6;
                s1.ep = i;
            }
            else s1.st[i] = 0;
        }
        
        s1.dist = 0;
        s1.dta = cal(s1);
        vis1[s1.dta][s1.ep] = true;
        que1.push(s1);
        // s1 finished
        
        _for(i, 0, 9) {
            char ch;
            cin >> ch;
            if(ch == 'E') s2.ep = i;
            tar[i] = ch;
        }
        
        dfs(s2, 0);
        
        //debug(que1.size());
        //debug(que2.size());
        //printf("====\n");
        
        int ans = 0;
        if(bfs(ans)) printf("%d\n", ans);
        else printf("-1\n");
    }
}

但是上面的优化还不足以通过POJ的数据
需要进一步优化

状态压缩位运算，哈希，双向bfs

面对类似的左右移动，穿插问题，可以想到
位运算

哈希表先封装起来

class HASH {
public:
    struct Node {
        int nxt, val;
    } nodes[HASHSZ];
    
    int head[HASHSZ];
    // head store the value of id
    int tot;
    
    void init() {
        Set(head, -1);
        tot = 0;
    }
    
    void insert(int hashV, int val) {
        nodes[tot].val = val;
        nodes[tot].nxt = head[hashV];
        head[hashV] = tot++;
    }
    
    int find(int dta) {
        int hashV = dta % HASHSZ;
        int i;
        for(i = head[hashV]; ~i; i = nodes[i].nxt) {
            int val = nodes[i].val;
            if(val == dta) return i;
        }
        insert(hashV, dta);
        return tot - 1;
    }
};

HASH hashTb;
void initHash() {
    hashTb.init();
}

位运算模拟

算法分析

POJ3131-4
POJ3131-5

双向bfs处理的时候，需要特判初始状态和末状态相等的情况
这时候最小步数是0

//
//  main.cpp
//  POJ3131-4
//
//  Created by zhangmin chen on 2019/7/22.
//  Copyright © 2019 zhangmin chen. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <bitset>
#include <assert.h>

using namespace std;
typedef long long llong;
typedef set<int>::iterator ssii;

const int HASHSZ = 5000007;
const int maxn = 5000007;

#define Cmp(a, b) memcmp(a, b, sizeof(b))
#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define Set(a, v) memset(a, v, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define _forS(i, l, r) for(set<int>::iterator i = (l); i != (r); i++)
#define _rep(i, l, r) for(int i = (l); i <= (r); i++)
#define _for(i, l, r) for(int i = (l); i < (r); i++)
#define _forDown(i, l, r) for(int i = (l); i >= r; i--)
#define debug_(ch, i) printf(#ch"[%d]: %d\n", i, ch[i])
#define debug_m(mp, p) printf(#mp"[%d]: %d\n", p->first, p->second)
#define debugS(str) cout << "dbg: " << str << endl;
#define debugArr(arr, x, y) _for(i, 0, x) { _for(j, 0, y) printf("%c", arr[i][j]); printf("\n"); }
#define _forPlus(i, l, d, r) for(int i = (l); i + d < (r); i++)

class HASH {
public:
    struct Node {
        int nxt, val;
    } nodes[HASHSZ];
    
    int head[HASHSZ];
    // head store the value of id
    int tot;
    
    void init() {
        Set(head, -1);
        tot = 0;
    }
    
    void insert(int hashV, int val) {
        nodes[tot].val = val;
        nodes[tot].nxt = head[hashV];
        head[hashV] = tot++;
    }
    
    int find(int dta) {
        int hashV = dta % HASHSZ;
        int i;
        for(i = head[hashV]; ~i; i = nodes[i].nxt) {
            int val = nodes[i].val;
            if(val == dta) return i;
        }
        insert(hashV, dta);
        return tot - 1;
    }
};

HASH hashTb;
void initHash() {
    hashTb.init();
}

bool vis1[maxn], vis2[maxn];
void initVis() {
    Set(vis1, 0);
    Set(vis2, 0);
}

class StNode {
public:
    int state;
    int pos;
    int dist;
    
    StNode(int s = 0, int p = 0, int dist = 0) : state(s), pos(p), dist(dist) {}
};

const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, -1, 0, 1};
// const int UP = 0, LEFT = 1, DOWN = 2, RIGHT = 3;

/*
 if(top == W && face == R) return 1;
 if(top == W && face == B) return 2;
 if(top == R && face == W) return 3;
 if(top == R && face == B) return 4;
 if(top == B && face == W) return 5;
 if(top == B && face == R) return 6;
 */

// const int Move[0][dir]
// const int Move[1][dir]
// UP LEFT DOWN RIGHT
// Move[1][UP] = (R, W)  Move[1][LEFT] = (B, R) Move[0][DOWN] = (R, W)  Move[0][RIGHT] = (B, R)
// Move[2][UP] = (B, W)  Move[2][LEFT] = (R, B)
// Move[3][UP] = (W, R)  Move[3][LEFT] = (B, W)
// Move[4][UP] = (B, R)  Move[4][LEFT] = (W, B)
// Move[5][UP] = (W, B)  Move[6][LEFT] = (R, W)
// Move[6][UP] = (R, B)  Move[6][LEFT] = (W, R)

const int Move[7][4] = {
    {0, 0, 0, 0},
    {3, 6, 3, 6},
    {5, 4, 5, 4},
    {1, 5, 1, 5},
    {6, 2, 6, 2},
    {2, 3, 2, 3},
    {4, 1, 4, 1}
};
// usage: int newCode = Move[oldCode][dir]

queue<StNode> que1, que2;
char tar[11];
int tep;

void initQue() {
    while(!que1.empty()) que1.pop();
    while(!que2.empty()) que2.pop();
}

int getBit(int state, int k) {
    return ( ( (state >> (3 * k + 2)) & 1 ) << 2 ) |
           ( ( (state >> (3 * k + 1)) & 1 ) << 1 ) |
           ( ( (state >> (3 * k)) & 1 ));
}


void dfs(int d, int state, int tep) {
    if(d == 9) {
        StNode cur(state, tep, 0);
        que2.push(cur);
        
        int dta2 = hashTb.find(state);
        vis2[dta2] = 1;
        return;
    }
    
    if(tar[d] == 'E') {
        dfs(d + 1, state << 3, tep);
        return;
    }
    
    int v1, v2;
    if(tar[d] == 'W') {
        v1 = 1; v2 = 2;
    }
    else if(tar[d] == 'R') {
        v1 = 3; v2 = 4;
    }
    else {
        v1 = 5; v2 = 6;
    }
    
    dfs(d + 1, (state << 3) | v1, tep);
    dfs(d + 1, (state << 3) | v2, tep);
}

// const int UP = 0, LEFT = 1, DOWN = 2, RIGHT = 3;
inline void update(StNode& u, int dir) {
    if(dir == 0) {
        //
        int np = u.pos - 3;
        int bit = getBit(u.state, 8 - np);
        
        int nbit = Move[bit][dir];
        u.state = (u.state ^ ( bit << ((8 - np) * 3) )) | ( nbit << ((8 - np - 3) * 3) );
        u.dist++;
        u.pos = np;
    }
    else if(dir == 1) {
        int np = u.pos - 1;
        int bit = getBit(u.state, 8 - np);
        
        int nbit = Move[bit][dir];
        u.state = (u.state ^ ( bit << ((8 - np) * 3) )) | ( nbit << ((8 - np - 1) * 3) );
        u.dist++;
        u.pos = np;
    }
    else if(dir == 2) {
        int np = u.pos + 3;
        int bit = getBit(u.state, 8 - np);
        
        int nbit = Move[bit][dir];
        u.state = (u.state ^ ( bit << ((8 - np) * 3) )) | ( nbit << ((8 - np + 3) * 3) );
        u.dist++;
        u.pos = np;
    }
    else if(dir == 3) {
        int np = u.pos + 1;
        int bit = getBit(u.state, 8 - np);
        
        int nbit = Move[bit][dir];
        u.state = (u.state ^ ( bit << ((8 - np) * 3) )) | ( nbit << ((8 - np + 1) * 3) );
        u.dist++;
        u.pos = np;
    }
}

bool valid(int x, int y) {
    if(0 <= x && x < 3 && 0 <= y && y < 3) return true;
    return false;
}

int bfs() {
    const int DEP1 = 20, DEP2 = 9;
    int lv1 = 0, lv2 = 0;
    
    for(lv1 = 0; lv1 <= DEP1; lv1++) {
        while (!que1.empty() && que1.front().dist == lv1) {
            // do something
            StNode x = que1.front(); que1.pop();
            int ex = x.pos / 3, ey = x.pos % 3;
            _for(dir, 0, 4) {
                int nx = ex + dx[dir], ny = ey + dy[dir];
                if(!valid(nx, ny)) continue;
                
                StNode clone = x;
                update(clone, dir);
                int hashV = hashTb.find(clone.state);
                
                if(!vis1[hashV]) {
                    vis1[hashV] = true;
                    if(vis2[hashV]) return lv1 + lv2 + 1;
                    que1.push(clone);
                }
            }
        }
        
        while(!que2.empty() && que2.front().dist == lv2 && lv2 < DEP2) {
            // do something
            StNode x = que2.front(); que2.pop();
            int ex = x.pos / 3, ey = x.pos % 3;
            _for(dir, 0, 4) {
                int nx = ex + dx[dir], ny = ey + dy[dir];
                if(!valid(nx, ny)) continue;
                
                StNode clone = x;
                update(clone, dir);
                int hashV = hashTb.find(clone.state);
                
                if(!vis2[hashV]) {
                    vis2[hashV] = true;
                    if(vis1[hashV]) return lv1 + lv2 + 2;
                    que2.push(clone);
                }
            }
        }
        
        if(lv2 < DEP2) lv2++;
    }
    return -1;
}


int main() {
    freopen("input.txt", "r", stdin);
    
    int ex, ey;
    while (scanf("%d%d", &ex, &ey) != EOF && ex && ey) {
        initVis();
        initQue();
        initHash();
        ex--; ey--;
        int ep = ey * 3 + ex;
        
        StNode s(0, ep, 0);
        _for(i, 0, 9) {
            s.state <<= 3;
            if(i == ep) continue;
            s.state |= 1;
        }
        que1.push(s);
        
        int dta1 = hashTb.find(s.state);
        vis1[dta1] = 1;
        // get start state finished
        
        
        // then get end status
        char c[3];
        _for(i, 0, 3) _for(j, 0, 3) {
            scanf("%s", c);
            tar[i * 3 + j] = c[0];
            if(c[0] == 'E') tep = i * 3 + j;
        }
        
        // judge 0
        int i;
        for(i = 0; i < 9; i++) {
            if(tar[i] == 'W' && i != s.pos) continue;
            if(tar[i] == 'E' && i == s.pos) continue;
            else break;
        }
        if(i == 9) {
            printf("0\n");
            continue;
        }
        
        // then add all 256 situation to the end queue
        dfs(0, 0, tep);
        // printf("%d\n", que2.size());
        
        // then double-way bfs
        printf("%d\n", bfs());
    }
}

八皇后的解答树填空

从 $[\text{cur}, N \cdot M]$ 位置中任选一个位置填空
代码如下

bool dfs(int cur, int d, int maxd) {
    if(d == maxd) {
        return true or false;
    }

    _for(i, cur, N * M) {
        fill the blank in Chessboard[i]
        if(dfs(i + 1, d + 1, maxd)) return true;
        reset Chessboard[i]
    }
    return false;
}

状态压缩搜索

UVA12569

//
//  main.cpp
//  UVA12569
//
//  Created by zhangmin chen on 2019/7/25.
//  Copyright © 2019 zhangmin chen. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <bitset>
#include <assert.h>

using namespace std;
typedef long long llong;
typedef set<int>::iterator ssii;

const int maxn = 15 + 5;

#define Cmp(a, b) memcmp(a, b, sizeof(b))
#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define Set(a, v) memset(a, v, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define _forS(i, l, r) for(set<int>::iterator i = (l); i != (r); i++)
#define _rep(i, l, r) for(int i = (l); i <= (r); i++)
#define _for(i, l, r) for(int i = (l); i < (r); i++)
#define _forDown(i, l, r) for(int i = (l); i >= r; i--)
#define debug_(ch, i) printf(#ch"[%d]: %d\n", i, ch[i])
#define debug_m(mp, p) printf(#mp"[%d]: %d\n", p->first, p->second)
#define debugS(str) cout << "dbg: " << str << endl;
#define debugArr(arr, x, y) _for(i, 0, x) { _for(j, 0, y) printf("%c", arr[i][j]); printf("\n"); }
#define _forPlus(i, l, d, r) for(int i = (l); i + d < (r); i++)

int read() {
    int x;
    scanf("%d", &x);
    return x;
}

template <typename T>
class Mempool {
public:
    vector<T*> buf;
    T* create() {
        buf.push_back(new T());
        return buf.back();
    }
    
    void reset() {
        _for(i, 0, buf.size()) delete buf[i];
        buf.clear();
    }
};

class Node {
public:
    int from, to;
    Node* nxt;
};

class State {
public:
    Node* path;
    int st, dist;
    State(int s = 0, int d = 0, Node* p = NULL) : st(s), dist(d), path(p) {}
    
    inline void setOBS(int u) {
        st |= (1 << (4 + u));
    }
    inline void resetOBS(int u) {
        st &= ~(1 << (4 + u));
    }
    
    inline bool existOB(int u) const {
        return st & (1 << (4 + u));
    }
    
    inline void setROB(int ru) {
        st = ((st >> 4) << 4) | ru;
    }
    inline int getROB() const {
        //
        return st & 0xf;
    }
};



Mempool<Node> pools;

Node* newNode(Node* nxt = NULL, int from = -1, int to = -1) {
    Node* p = pools.create();
    p->nxt = nxt;
    p->from = from;
    p->to = to;
    return p;
}

vector<int> G[maxn];
int vis[1 << 19];
int obs[maxn];
queue<State> que;

int N, M, S, T;

void init() {
    _for(i, 0, maxn) G[i].clear();
    Set(vis, 0);
    Set(obs, 0);
    
    while(!que.empty()) que.pop();
}

void initBFS() {
    //
    State beg;
    _for(i, 0, M) beg.setOBS(obs[i]);
    beg.setROB(S);
    
    que.push(beg);
    // debug(beg.st);
    vis[beg.st] = 1;
}

void Move(const State& St, int u, queue<State>& que) {
    // Move from u -> v
    
    int RPOS = St.getROB();
    
    _for(i, 0, G[u].size()) {
        //
        int v = G[u][i];
        State cur = St;
        if(v == RPOS || cur.existOB(v)) continue;
        
        if(u == RPOS) {
            //
            cur.st = ((St.st >> 4) << 4) | v;
            // debug(cur.st);
        }
        else {
            //
            cur.st ^= (1 << (4 + u));
            cur.st |= (1 << (4 + v));
        }
        
        if(vis[cur.st]) continue;
        vis[cur.st] = 1;
        State nxt(cur.st, St.dist + 1, newNode(St.path, u, v));
        que.push(nxt);
    }
}

ostream& operator<< (ostream& os, Node* p) {
    if(p == NULL) return os;
    os << p->nxt << p->from + 1 << " " << p->to + 1 << endl;
    return os;
}

void BFS() {
    //
    initBFS();
    while (!que.empty()) {
        const State x = que.front();
        // debug(x.getROB());
        // debug(T);
        que.pop();
        
        if(x.getROB() == T) {
            printf("%d\n", x.dist);
            cout << x.path;
            return;
        }
        
        Move(x, x.getROB(), que);
        _for(i, 0, N) if(x.existOB(i)) Move(x, i, que);
    }
    cout << "-1" << endl;
}

int main() {
    freopen("input.txt", "r", stdin);
    int kase = read();
    
    _rep(t, 1, kase) {
        init();
        scanf("%d%d%d%d", &N, &M, &S, &T);
        S--; T--;
        
        printf("Case %d: ", t);
        
        _for(i, 0, M) obs[i] = read() - 1;
        
        _for(i, 0, N - 1) {
            int u = read() - 1, v = read() - 1;
            G[u].push_back(v);
            G[v].push_back(u);
        }
        
        // then we finished input
        // initBFS and BFS
        BFS();
        pools.reset();
        cout << endl;
    }
}

状态压缩搜索练习

LA2093

//
//  main.cpp
//  LA2093
//
//  Created by zhangmin chen on 2019/7/27.
//  Copyright © 2019 zhangmin chen. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <bitset>
#include <assert.h>
#include <unordered_set>

using namespace std;
typedef long long llong;
typedef set<int>::iterator ssii;


#define Cmp(a, b) memcmp(a, b, sizeof(b))
#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define Set(a, v) memset(a, v, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define _forS(i, l, r) for(set<int>::iterator i = (l); i != (r); i++)
#define _rep(i, l, r) for(int i = (l); i <= (r); i++)
#define _for(i, l, r) for(int i = (l); i < (r); i++)
#define _forDown(i, l, r) for(int i = (l); i >= r; i--)
#define debug_(ch, i) printf(#ch"[%d]: %d\n", i, ch[i])
#define debug_m(mp, p) printf(#mp"[%d]: %d\n", p->first, p->second)
#define debugS(str) cout << "dbg: " << str << endl;
#define debugArr(arr, x, y) _for(i, 0, x) { _for(j, 0, y) printf("%c", arr[i][j]); printf("\n"); }
#define _forPlus(i, l, d, r) for(int i = (l); i + d < (r); i++)

const int N = 15;
const int D = 6;

const int DIR[N + 1][D] = {
    {0, 0, 0, 0, 0, 0}, // 0
    {0, 0, 0, 0, 2, 3}, // 1
    {0, 1, 0, 3, 4, 5}, // 2
    {1, 0, 2, 0, 5, 6}, // 3
    {0, 2, 0, 5, 7, 8}, // 4
    {2, 3, 4, 6, 8, 9}, // 5
    {3, 0, 5, 0, 9, 10}, // 6
    {0, 4, 0, 8, 11, 12}, // 7
    {4, 5, 7, 9, 12, 13}, // 8
    {5, 6, 8, 10, 13, 14}, // 9
    {6, 0, 9, 0, 14, 15}, // 10
    {0, 7, 0, 12, 0, 0}, // 11
    {7, 8, 11, 13, 0, 0}, // 12
    {8, 9, 12, 14, 0, 0}, // 13
    {9, 10, 13, 15, 0, 0}, // 14
    {10, 0, 14, 0, 0, 0} // 15
};

template<typename T>
ostream& operator<< (ostream& os, const vector<T>& vec) {
    _for(i, 0, vec.size()) {
        if(i != 0) os << " ";
        os << vec[i];
    }
    return os;
}

class Board {
public:
    int st, cnt;
    vector<int> path;
    
    Board() {
        st = 0b1111111111111111;
        cnt = N;
        path.clear();
    }
    
    bool isEmpty(int i) const {
        if((st & (1 << i)) != 0) return false;
        else return true;
    }
    
    void clear(int i) {
        assert(!isEmpty(i));
        st ^= (1 << i);
        cnt--;
    }
    
    void put(int i) {
        assert(isEmpty(i));
        st |= (1 << i);
        cnt++;
    }
    
    int jumpTo(int i, int d) const {
        // follow the direction d to jump to xxx
        int to = DIR[i][d];
        if(!to || isEmpty(to)) return 0;
        // 0 is nil, means can not jump
        
        while(to && !isEmpty(to)) to = DIR[to][d];
        return to;
    }
    
    void dbg() {
        int len = 1, p = 1;
        cout << "cnt = " << cnt << endl;
        
        _rep(i, 1, N) {
            if(isEmpty(i)) cout << "_";
            else cout << "*";
            
            if(i == p) {
                cout << endl;
                len += 1; p += len;
            }
        }
        
        cout << endl;
        cout << path.size() << " -> " << path << endl;
    }
};

// Board bd;
queue<Board> que;
unordered_set<int> vis;

void init() {
    while(!que.empty()) que.pop();
    vis.clear();
}

void initBFS(int x) {
    Board bd;
    bd.clear(x);
    que.push(bd);
    vis.insert(bd.st);
}

void bfs(int x) {
    // x is init empty place
    initBFS(x);
    
    while (!que.empty()) {
        Board cur = que.front();
        que.pop();
        
        if(cur.cnt == 1 && !cur.isEmpty(x)) {
            // founded! print ans
            cout << cur.path.size() / 2 << endl;
            cout << cur.path << endl;
            return;
        }
        
        // then find next
        _rep(i, 1, N) {
            if(cur.isEmpty(i)) continue;
            
            _for(d, 0, D) {
                // jump to the next
                int to = cur.jumpTo(i, d);
                if(!to) continue;
                
                // i --dir d--> to
                Board nxtb = cur;
                assert(nxtb.isEmpty(i) == false);
                
                nxtb.clear(i);
                int j = DIR[i][d];
                while(j != to) {
                    nxtb.clear(j);
                    j = DIR[j][d];
                }
                // [i, to] in direction d, is all cleared
                
                // then put ball in hole to
                nxtb.put(to);
                if(vis.count(nxtb.st)) continue;
                
                vis.insert(nxtb.st);
                nxtb.path.push_back(i);
                nxtb.path.push_back(to);
                
                que.push(nxtb);
            }
        }
        
    }
    
    cout << "IMPOSSIBLE\n";
}


int main() {
    freopen("input.txt", "r", stdin);
    int T;
    scanf("%d", &T);
    
    while (T--) {
        // bfs(int x)
        // x is empty point
        
        init();
        int x;
        scanf("%d", &x);
        
        bfs(x);
    }
}