HDU 1401 Solitaire 双向DFS

题意

给定一个\(8*8\)的棋盘，棋盘上有4个棋子。每一步操作可以把任意一个棋子移动到它周围四个方向上的空格子上，或者可以跳过它四个方向上的棋子（就像跳棋那样）。给定初始状态和末状态，问能否在8步之内，从初始状态变换到末状态。

解题思路

这是是看的学长写的题解，很好，也算自己简单知道了双向BFS是什么情况了。

给定了初始状态和末状态，又有最多只能走8步的限制，所以我们很容易就可以想到进行双向BFS。但是一定要注意对冗余状态的剪枝。我们可以对这四枚棋子按照某种顺序进行排序，这样就可以去掉很多等效局面，大大降低时间复杂度。

我们可以通过Hash，把一个局面Hash成一个整数\(hashVal\)，然后用\(vis[hashVal]\)来记录达到这个局面一共走了多少步。当搜索结果相交的时候，判断一下当前的步数是否小于等于8即可，具体见代码。

这里还要注意，因为是双向BFS，所以每次循环这两个BFS都会走一步，因而每个BFS最多只能走4步

代码实现

#include <map>

#include <queue>

#include <cstdio>

#include <algorithm>

using namespace std;

typedef long long ll;

const ll BASE = 100;

const int MAXN = 8 + 2;

const int nextS[][2] = {{1,  0}, {0,  1}, {-1, 0}, {0,  -1}};

int mp[MAXN][MAXN];

struct Node {

    int x[4], y[4];

} st, ed;

inline bool check(int x,int y)

{

	if (x > 8 || x < 1 || y > 8 || y < 1) return false;

	else return true;

}

//专门写的一个哈希函数，对于每个状态转化为一个数，这里是真的难

ll getHashVal(Node a) {

    int temp[4];

    ll ret = 0;

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

        temp[i] = (a.x[i] - 1) * 8 + a.y[i];

    sort(temp, temp + 4);

    for (int i = 3; i >= 0; i--)

        ret = ret * BASE + temp[i];

    return ret;

}

bool bfs() {

    int step = 0;

    queue<Node> q1, q2;

    map<ll, int> vis1, vis2;

    Node now, temp;

    q1.push(st), q2.push(ed);

    vis1[getHashVal(st)] = 0, vis2[getHashVal(ed)] = 0;

    while (true)

	{

        now = q1.front();

        q1.pop();

        int nowHashVal = getHashVal(now);

        if (vis1[nowHashVal] > 4) break;//这里大于4就要跳出

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

            mp[now.x[i]][now.y[i]] = 1;

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

		{

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

			{

                int nextX = now.x[i] + nextS[j][0], nextY = now.y[i] + nextS[j][1];

                if (check(nextX, nextY)==false) continue;

                if (mp[nextX][nextY]) //如果这个点有棋子了，那么就要跳过再走一次。

				{

                    nextX += nextS[j][0], nextY += nextS[j][1];

                    if (check(nextX, nextY)==false || mp[nextX][nextY]) continue;

                }

                temp = now;

                temp.x[i] = nextX, temp.y[i] = nextY;

                int tempHashVal = getHashVal(temp);

                if (vis1.find(tempHashVal) == vis1.end())

				{

                    vis1[tempHashVal] = vis1[nowHashVal] + 1;

                    q1.push(temp);

                    if (vis2.find(tempHashVal) != vis2.end())//查找反向bfs中有没有走到这个节点的

					{

                        step = vis1[tempHashVal] + vis2[tempHashVal];

                        if (step <= 8) return true;

                    }

                }

            }

        }

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

            mp[now.x[i]][now.y[i]] = 0;

        now = q2.front();

        q2.pop();

        nowHashVal = getHashVal(now);

        if (vis2[nowHashVal] > 4)break;

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

		{

            mp[now.x[i]][now.y[i]] = 1;

        }

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

		{

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

			{

                int nextX = now.x[i] + nextS[j][0], nextY = now.y[i] + nextS[j][1];

                if (check(nextX, nextY)==false) continue;

                if (mp[nextX][nextY])

				{

                    nextX += nextS[j][0], nextY += nextS[j][1];

                     if (check(nextX, nextY)==false || mp[nextX][nextY]) continue;

                }

                temp = now;

                temp.x[i] = nextX, temp.y[i] = nextY;

                int tempHashVal = getHashVal(temp);

                if (vis2.find(tempHashVal) == vis2.end())

				{

                    vis2[tempHashVal] = vis2[nowHashVal] + 1;

                    q2.push(temp);

                    if (vis1.find(tempHashVal) != vis1.end())

					{

                        step = vis1[tempHashVal] + vis2[tempHashVal];

                        if (step <= 8) return true;

                    }

                }

            }

        }

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

            mp[now.x[i]][now.y[i]] = 0;

    }

    return false;

}

int main() {

    while (scanf("%d %d", &st.x[0], &st.y[0]) != EOF) {

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

            scanf("%d %d", &st.x[i], &st.y[i]);

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

            scanf("%d %d", &ed.x[i], &ed.y[i]);

        if (getHashVal(st) == getHashVal(ed)) {

            printf("YES\n");

            continue;

        }

        printf(bfs() ? "YES\n" : "NO\n");

    }

    return 0;

}