题目描述：

棋盘上有4个棋子，棋子的移动满足“跳棋”的规则。

给你两个棋盘的状态，问你能不能8步之内从第一个状态变成第二个状态。

解题报告：

单向广搜的话，

每一步：
由于4个棋子都有四个方向可以走动，所以状态有16个。

16的8次方，没有强力剪枝的话，明显超时。

双向广搜：

16的4次方乘以2就是复杂度。

注意：记录走过状态的vst数组的四个点是要排好序的。

因为四个点可以无序，两个棋盘状态的棋子不要求是一一对应的。

代码自认为比较精简，如下：

#include<iostream>
#include<algorithm>
using namespace std;
bool vst[2][8][8][8][8][8][8][8][8];
struct pint{int x, y;};
bool cmp(pint a, pint b)
{
    if (a.x == b.x) return a.y < b.y;
    return a.x < b.x;
}
struct ele
{
    int step;
    pint p[4];
}pos[2], que[2][700000];
int move[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
void setvst(ele x, int id)
{
    sort(x.p, x.p + 4, cmp);
    vst[id][x.p[0].x][x.p[0].y][x.p[1].x][x.p[1].y][x.p[2].x][x.p[2].y][x.p[3].x][x.p[3].y] = 1;
}
bool getvst(ele x, int id)
{
    sort(x.p, x.p + 4, cmp);
    return vst[id][x.p[0].x][x.p[0].y][x.p[1].x][x.p[1].y][x.p[2].x][x.p[2].y][x.p[3].x][x.p[3].y];
}
bool judge2(ele x, int id)
{
    return (x.p[id].x >= 0 && x.p[id].x < 8 && x.p[id].y >= 0 && x.p[id].y < 8 );
}
bool judge(ele x, int id)
{
    for(int i = 0; i < 4; i++)
        if (i == id) continue;
        else if (x.p[i].x == x.p[id].x && x.p[i].y == x.p[id].y) return true;
    return false;
}
int main()
{
    memset(vst, 0, sizeof(vst)); bool flag = false;
    int head[2], tail[2]; head[0] = head[1] = tail[0] = tail[1] = 0;
    for(int i = 0; i < 2; i++)
    {
        for(int j = 0; j < 4; j++)
        {
            scanf("%d%d", &pos[i].p[j].x, &pos[i].p[j].y);
            pos[i].p[j].x--, pos[i].p[j].y--;
        }
        setvst(pos[i], i); que[i][tail[i]].step = 0;
        que[i][tail[i]++] = pos[i];
    }
    for(int i = 0; head[i] < tail[i]; i = ((i + 1) % 2))
    {
        int pre = que[i][head[i]].step;
        while(head[i] < tail[i])
        {
            ele jeogia = que[i][head[i]];
            if (jeogia.step != pre) break;
            else head[i]++;
            for(int j = 0; j < 4; j++)
                for(int k = 0; k < 4; k++)
                {
                    que[i][tail[i]] = jeogia;
                    que[i][tail[i]].p[j].x += move[k][0];que[i][tail[i]].p[j].y += move[k][1];
                    if (judge2(que[i][tail[i]], j) && judge(que[i][tail[i]], j))
                    {
                        que[i][tail[i]].p[j].x += move[k][0];
                        que[i][tail[i]].p[j].y += move[k][1];
                    }
                    if (judge2(que[i][tail[i]], j) && !judge(que[i][tail[i]], j) && !getvst(que[i][tail[i]], i))
                    {
                        setvst(que[i][tail[i]], i);
                        que[i][tail[i]].step = jeogia.step + 1;
                        if (que[i][tail[i]].step <= 4 && getvst(que[i][tail[i]], i ^ 1))
                        {
                            flag = true;
                            goto lable;
                        }
                        if (que[i][tail[i]].step < 4) tail[i]++;
                    }
                }
        }
    }
    lable: flag ? printf("YES\n") : printf("NO\n");
    return 0;
}