solitaire(双向bfs＋状态压缩).cpp

杭电acm解题报告2001---2099.

//类似跳跳棋的走法，实现上没什么问题，主要是状态的保存
//8×8的矩阵每个点的x，y排列后，可以当作8进制来转换，状态数则为8^8
//再位压缩，unsigned int占32位，因为用到了双向bfs，状态有3种
//00	未访问
//10	S(起点)访问过	
//01	E(终点)访问过
//32/2 = 16，即一个unsigned int保存16个状态，所以压缩后空间为8^8/16 = 1048576
#include <cstdio>
#include <string>
#include <queue>
#include <algorithm>
using namespace std;
unsigned int hash[1048576+100];
int dic[4][2] =
{{1,0},{-1,0},{0,1},{0,-1}};
struct node {
    short p[4][2];
    short t;
    char from;
    bool turn(int sp, int d) {
        p[sp][0] += dic[d][0];
        p[sp][1] += dic[d][1];
        t ++;
        if (p[sp][0] <0 || p[sp][1] <0 || p[sp][0] >=8 || p[sp][1] >=8) {
            return false;
        }
		int i,j;
        for (i=0;i<4;i++) {
            if (i != sp) {
                if (p[i][0] == p[sp][0] && p[i][1] == p[sp][1]) {
                    p[sp][0] += dic[d][0];
                    p[sp][1] += dic[d][1];
					if (p[sp][0] <0 || p[sp][1] <0 || p[sp][0] >=8 || p[sp][1] >=8) {
						return false;
					}
                    for (j=0;j<i;j++) {
                        if (j != sp) {
                            if (p[j][0] == p[sp][0] && p[j][1] == p[sp][1]) {
                                return false;
                            }
                        }
                    }//for j
                }
            }
        }
        return true;
    }
};
node ns,ne;
queue<node> SQ;

inline int make_hash(short p[4][2])
{
    int v[4],hv,i;
    for (i=0;i<4;i++) {
        v[i] = p[i][0]*8 + p[i][1];
    }
    sort(v,v+4);
    hv = 0;
    for (i=0;i<4;i++) {
        hv = hv*64 + v[i];
    }
    return hv;
}

inline unsigned int get_hash(int v)
{
	unsigned int t = hash[v>>4];
	unsigned int f = 1 << 2*(v%16);
	f |= 1 << (2*(v%16) +1);
	t &= f;
	t >>= 2*(v%16);
	return t;
}

inline void set_hash(int v,char from)
{
	unsigned int t = hash[v>>4];
	unsigned int f = 0;
	if (from == 'S') {
		f = 1 << 2*(v%16) +1;
	}
	else {
		f = 1 << 2*(v%16);
	}
	hash[v>>4] = t | f;
}

bool bfs()
{
    node now,next;
    int l,i,j;
    while (!SQ.empty()) {
        l = SQ.size();
        while (l--) {
            now = SQ.front();
            SQ.pop();

            if (now.t >= 4) {
                return false;
            }
            for (i=0;i<4;i++) {
                for (j=0;j<4;j++) {
                    next = now;
                    if (next.turn(i,j)) {
                        int t = make_hash(next.p);
						int h = get_hash(t);
						h = get_hash(t);
                        if (h == 0) {
                            set_hash(t,next.from);
                            SQ.push(next);
                        }
                        else if (h == 2) {
                            if (next.from == 'E') {
                                return true;
                            }
                        }
                        else {
                            if (next.from == 'S') {
                                return true;
                            }
                        }
                    }
                }//for j
            }//for i
        }
    }
    return false;
}

int main()
{
	int i;
    while (scanf("%d %d %d %d %d %d %d %d",&ns.p[0][0],&ns.p[0][1],&ns.p[1][0],&ns.p[1][1],&ns.p[2][0],&ns.p[2][1],&ns.p[3][0],&ns.p[3][1]) == 8) {
        memset(hash,0,sizeof(hash));
        int l = SQ.size();
        while (l--) {
            SQ.pop();
        }
        scanf("%d %d %d %d %d %d %d %d",&ne.p[0][0],&ne.p[0][1],&ne.p[1][0],&ne.p[1][1],&ne.p[2][0],&ne.p[2][1],&ne.p[3][0],&ne.p[3][1]);
        for (i=0;i<4;i++) {
			ns.p[i][0] --;	ns.p[i][1] --;
			ne.p[i][0] --;	ne.p[i][1] --;
        }
		ns.t = 0;    ns.from = 'S';
		set_hash(make_hash(ns.p),'S');
        ne.t = 0;    ne.from = 'E';
		set_hash(make_hash(ne.p),'E');
        SQ.push(ns);
        SQ.push(ne);
        if (bfs()) {
            printf("YES\n");
        }
        else {
            printf("NO\n");
        }
    }
}