题目跳转

HDOJ-1401

题目大意

8*8的棋盘给你四个点的整体的始末状态（貌似不需要一一对应）
移动方式为十字移动，并且在遇到别的棋子的时候，能够一次跳两格。
问是否能在8步之内到达目标位置

思路

双向广搜 - 棋子位置排序 - 哈希

1. 双向广搜

   • 先采用哪个队列的小，扩展哪个，尽量使得两边的状态数相近。然而只采取这样，会导致一个因为合法状态数过少而使扩展过早Done，使得无法搜出答案。（面向数据是把每个状态的最大步数设为5可过）
   • 最后还没搜出答案，再扩展未空的队列。

2. 棋子位置排序

   • 题目似乎没有明确说明棋子位置是否一一对应。
   • 如果不是，让棋子排序，可以使得多个状态化而为一个，大大减小搜取的数据量。

3. 哈希

   • 观察得，每一位不超过10，转为int后最大的数为88878685，当然采用八进制可以更小，因此采用把点位转为int
   • 我一开始采用string，纯纯犯傻了，剩下的变量名s，由此得来（（（

CODE

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <queue>
#include <map>

using namespace std;

typedef pair<int, int> PII;

struct Node
{
    PII p[4];
    int s = 0;
    int toint()
    {
        int t = 0;
        for (int i = 0; i < 4; i++)
        {
            t = t * 10 + this->p[i].first;
            t = t * 10 + this->p[i].second;
        }
        return t;
    }
    friend bool operator<(const Node &a, const Node &b)
    {
        return a.s < b.s;
    }
} st[2];

int dxy[4][2] = {
    {0, 1},
    {1, 0},
    {0, -1},
    {-1, 0},
};
map<int, int> d[2];
// 未用到
bool read_data()
{
    for (int i = 0; i < 2; i++)
        for (int j = 0; j < 4; j++)
            cin >> st[i].p[j].first >> st[i].p[j].second;
    return true;
}
// 判断是否P点已被别的棋子占用
bool used_pos(PII p, Node t)
{
    //    cout << "used_posxxxx\n";
    //    cout << p.first << ' ' << p.second << endl;
    for (int i = 0; i < 4; i++)
    {
        //        cout << t.p[i].first << ' ' << t.p[i].second << endl;
        if (t.p[i] == p)
            return true;
    }
    //    cout << endl;
    return false;
    ;
}
// 队列q扩展一次
int expand(queue<Node> &q, map<int, int> &mp1, map<int, int> &mp2)
{
    Node t = q.front();
    q.pop();

    for (int i = 0; i < 4; i++) // which change
    {
        int x = t.p[i].first, y = t.p[i].second;
        for (int j = 0; j < 4; j++) // direction
        {
            int nx = x + dxy[j][0], ny = y + dxy[j][1];
            if (nx < 1 || nx > 8 || ny < 1 || ny > 8)
                continue;
            if (used_pos(make_pair(nx, ny), t))
            {
                nx += dxy[j][0], ny += dxy[j][1];
                if (nx < 1 || nx > 8 || ny < 1 || ny > 8)
                    continue;
                if (used_pos(make_pair(nx, ny), t))
                    continue;
            }
            // have found legal status, check if it had existed
            Node nt = t;
            nt.p[i] = make_pair(nx, ny), sort(nt.p, nt.p + 4), nt.s = nt.toint();

            if (!mp1.count(nt.s))
            {
                mp1[nt.s] = mp1[t.s] + 1;
                if (mp2.count(nt.s))
                    return mp1[nt.s] + mp2[nt.s];
                //    cout << mp1[nt.s] + mp2[nt.s] << endl;
                if (mp1[nt.s] == 4)
                    continue;
                q.push(nt);
            }
        }
    }
    return 9;
}
bool dbfs(Node A, Node Z)
{
    queue<Node> q[2];
    sort(A.p, A.p + 4), sort(Z.p, Z.p + 4);
    A.s = A.toint(), Z.s = Z.toint();
    q[0].push(A), q[1].push(Z);
    d[0][A.s] = 0, d[1][Z.s] = 0;

    while (q[0].size() && q[1].size())
    {
        int t;
        if (q[0].size() <= q[1].size())
            t = expand(q[0], d[0], d[1]);
        else
            t = expand(q[1], d[1], d[0]);
        if (t <= 8)
            return true;
    }
    for (int i = 0; i < 2; i++)
    {
        while (q[i].size())
        {
            int t;
            t = expand(q[i], d[i], d[1 - i]);
            if (t <= 8)
                return true;
        }
    }

    return false;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    //  freopen("i.txt", "r", stdin);
    //  freopen("o.txt", "w", stdout);
    while (cin >> st[0].p[0].first >> st[0].p[0].second)
    {
        for (int i = 0; i < 2; i++)
            d[i].clear();
        for (int i = 0; i < 2; i++)
            for (int j = 1 - i; j < 4; j++)
                cin >> st[i].p[j].first >> st[i].p[j].second;
        //        read_data();
        if (dbfs(st[0], st[1]))
            cout << "YES\n";
        else
            cout << "NO\n";
    }
    return 0;
}