Solitaire(双向BFS)

Solitaire is a game played on a chessboard 8x8. The rows and columns of the chessboard are numbered from 1 to 8, from the top to the bottom and from left to right respectively.
There are four identical pieces on the board. In one move it is allowed to:
> move a piece to an empty neighboring field (up, down, left or right),

> jump over one neighboring piece to an empty field (up, down, left or right).

 There are 4 moves allowed for each piece in the configuration shown above. As an example let's consider a piece placed in the row 4, column 4. It can be moved one row up, two rows down, one column left or two columns right.

Input:

Each of two input lines contains 8 integers a1, a2, ..., a8 separated by single spaces and describes one configuration of pieces on the chessboard. Integers a2j-1 and a2j (1 <= j <= 4) describe the position of one piece - the row number and the column number respectively. Process to the end of file.

Output:

The output should contain one word for each test case - YES if a configuration described in the second input line is reachable from the configuration described in the first input line in at most 8 moves, or one word NO otherwise.

Sample Input:

4 4 4 5 5 4 6 5

2 4 3 3 3 6 4 6

Sample Output

YES

题意：给你四个点的起始坐标，还有四个点的终点坐标；

在每一步中你可以让一个点往上下左右移动一格，如果移动一格后撞到其他的点上，你可以跳过这一格，既移动两格。

问是否能在最多八步完成。

//思路：我一开始想到是用一个九维数组来存它的转态，不过一直在爆内存；
//后来看了大佬们的博客后发现要用hash值来存，把四个点的坐标转换为一个8位数的数字就可以了；
//注意，转换数字时一定要先排序，否则会重复；
//再因为一些细节WA了几发后，终于A了

#define _CRT_SECURE_NO_WARNINGS
#include
#include
#include
#include
#include
#include
#include<set>
#include 
#include
#include    
#include
#include
#include
using namespace std;
#define inf 1<<30
#define eps 1e-7
#define LD long double
#define LL long long
#define maxn 100000005
int step = 0;
struct node
{
    int x[5] = {};
    int y[5] = {};
}start, last, t, v;
set<int>vis[2];
int dir[5][3] = { {1,0},{-1,0},{0,1},{0,-1} };
queueq[2];
int flag = 0;//旗帜
int number(node p)//转换为hash值
{
    int sum = 0;
    for (int i = 1; i <= 4; i++)
    {
        sum = sum * 100 + p.x[i] * 10 + p.y[i];
    }
    return sum;
}
void paixu(node& t)//对四个点排序
{
    int  x;
    for (int i = 1; i <= 4; i++)
    {
        x = i;
        for (int j = i + 1; j <= 4; j++)
            if (t.x[x] > t.x[j])
                x = j;
            else if (t.x[x] == t.x[j] && t.y[x] > t.y[j])
                x = j;
        swap(t.x[i], t.x[x]);
        swap(t.y[i], t.y[x]);
    }
}
int judge(node& w, int i)//判断一下是否合法，是否重复
{
    if (w.x[i] >= 1 && w.x[i] <= 8 && w.y[i] >= 1 && w.y[i] <= 8)
    {
        for (int j = 1; j <= 4; j++)
        {
            if (j == i)
            {
                continue;
            }
            if (w.x[i] == w.x[j] && w.y[i] == w.y[j])
            {
                return 1;
            }
        }
        return 0;
    }
    return 1;
}
void BFS(int k)//进行一次搜索
{
    int sum = q[k].size();//获得当前队列中要搜索的个数
    while (sum--)
    {
        t = q[k].front();
        q[k].pop();
        for (int i = 1; i <= 4; i++)//四个点嘛
        {
            for (int j = 0; j < 4; j++)//四个方向
            {
                v = t;
                v.x[i] = t.x[i] + dir[j][0];
                v.y[i] = t.y[i] + dir[j][1];
                if (judge(v, i) == 1)//撞到了格子，再走一步
                {
                    v.x[i] = v.x[i] + dir[j][0];
                    v.y[i] = v.y[i] + dir[j][1];
                    if (judge(v, i) == 1)
                    {
                        continue;
                    }
                }
                paixu(v);
                int num;
                num = number(v);
                if (vis[k].count(num)==1)continue;
                if (vis[1 - k].count(num)==1)
                {
                    flag = 1;
                    return;
                }
                vis[k].insert(num);
                q[k].push(v);
            }
        }
    }
}
void BBFS()
{
    int k;
    paixu(start);
    paixu(last);
    k = number(start);
    vis[0].insert(k);
    k = number(last);
    vis[1].insert(k);
    q[0].push(start);
    q[1].push(last);
    while (1)
    {
        if (q[0].size() < q[1].size())
        {
            BFS(0);
        }
        else
        {
            BFS(1);
        }
        step++;//记录步数
        if (step == 8)break;
        if (flag == 1)break;
    }
}
int main()
{
    while (scanf("%d%d", &start.x[1], &start.y[1]) != EOF)
    {
        vis[0].clear();
        vis[1].clear();
        flag = 0, step = 0;//初始化啊，WA了两发。。。。
        while (!q[0].empty())
        {
            q[0].pop();
        }
        while (!q[1].empty())
        {
            q[1].pop();
        }
        for (int i = 2; i <= 4; i++)
        {
            scanf("%d%d", &start.x[i], &start.y[i]);
        }
        for (int i = 1; i <= 4; i++)
        {
            scanf("%d%d", &last.x[i], &last.y[i]);
        }
        BBFS();
        if (flag)
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
}
ACM

相关

acm讲解

「acmhdu - 6314」Matrix

第十三届河南省ACM-ICPC游记

ACM模板

Hyperf 接入阿里云ACM应用配置管理中心

[ACM] BFS & 双端BFS & A* & 双边BFS

计算几何 / Geometry（ACM-Template 2.0）

ACM入门方式

Linux 下使用 acme.sh 配置 Let's Encrypt 免费 SSL 证书 + 通配符证书

如何写好一篇高质量的IEEE/ACM Transaction级别的计算机科学论文?

ACM- java在acm中的快速读入，多组读入，快速输出模板

ACM - 动态规划 - P1282 多米诺骨牌

标签