Solitaire

题目大意

每个棋子可以跳向上下左右四个方向的格子
如果格子上有棋子，可以跳过该棋子（最多跳一个）
并且保证不跳出边界
给出两个状态，每个状态包含四个棋子的坐标
问4步之内能否从第一个状态到达第二一个状态

Time: 1000 ms
Memory: 32768 kB

解题思路及分析

对每个棋子四个方向进行bfs
由于过程是可逆的，故可以进行双向搜索
访问标记每个状态时，可以把状态的4个坐标转成一个8位数来标记
原来unordered_map自定义键值类型需要自己写哈希函数……算了，转8位数标记一样的

AC代码

//#include <bits/stdc++.h>
#include <cstdio>
#include <queue>
#include <unordered_map>
#include <algorithm>
#include <cstring>
using namespace std;

struct Pos
{
    int x, y;
};

struct State
{
    Pos pos[4];
    int step;
};

bool cmp(Pos a, Pos b)
{
    return (a.x == b.x) ? (a.y < b.y) : (a.x < b.x);
}

// unordered_map<State, bool> vis1, vis2;
unordered_map<int, bool> vis1, vis2;
int mp[10][10];
int dx[] = { 1, 0, -1, 0 };
int dy[] = { 0, 1, 0, -1 };
bool ans;

bool judge(int x, int y)    // 判断是否在边界内
{
    return (1 <= x && x <= 8 && 1 <= y && y <= 8);
}

int to_num(State now)   // 转成8位数
{
    int res = 0;
    for (int i = 0; i < 4; i++)
    {
        res = res * 100 + now.pos[i].x * 10 + now.pos[i].y;
    }
    return res;
}

bool bfs(State s1, State s2)
{
    queue<State> q1, q2;
    State now, next;
    s1.step = 0;
    s2.step = 0;
    q1.push(s1);
    q2.push(s2);
    vis1[to_num(s1)] = true;
    vis2[to_num(s2)] = true;
    while ((!q1.empty()) || (!q2.empty()))
    {
        if (!q1.empty())
        {
            now = q1.front();
            q1.pop();
            memset(mp, 0, sizeof(mp));
            for (int k = 0; k < 4; k++)
            {
                mp[now.pos[k].x][now.pos[k].y] = 1;
            }
            if (now.step == 4)
            {
                continue;
            }
            if (vis2[to_num(now)])
            {
                return true;
            }
            for (int i = 0; i < 4; i++) // 枚举棋子
            {
                for (int j = 0; j < 4; j++) // 枚举几个方向
                {
                    next = now;
                    next.pos[i].x = next.pos[i].x + dx[j];
                    next.pos[i].y = next.pos[i].y + dy[j];
                    next.step = now.step + 1;
                    if (!judge(next.pos[i].x, next.pos[i].y))
                    {
                        continue;
                    }
                    if (mp[next.pos[i].x][next.pos[i].y] == 1)  // 是否需要跳过棋子
                    {
                        next.pos[i].x = next.pos[i].x + dx[j];
                        next.pos[i].y = next.pos[i].y + dy[j];
                    }
                    if (!judge(next.pos[i].x, next.pos[i].y))
                    {
                        continue;
                    }
                    sort(next.pos, next.pos + 4, cmp);
                    int goal = to_num(next);
                    if (vis2[goal])
                    {
                        return true;
                    }
                    if (!vis1[goal])
                    {
                        vis1[goal] = true;
                        q1.push(next);
                    }
                }
            }
        }
        if (!q2.empty())
        {
            now = q2.front();
            q2.pop();
            memset(mp, 0, sizeof(mp));
            for (int k = 0; k < 4; k++)
            {
                mp[now.pos[k].x][now.pos[k].y] = 1;
            }

            if (now.step == 4)
            {
                continue;
            }
            if (vis1[to_num(now)])
            {
                return true;
            }
            for (int i = 0; i < 4; i++) // 枚举棋子
            {
                for (int j = 0; j < 4; j++) // 枚举几个方向
                {
                    next = now;
                    next.pos[i].x = next.pos[i].x + dx[j];
                    next.pos[i].y = next.pos[i].y + dy[j];
                    next.step = now.step + 1;
                    if (!judge(next.pos[i].x, next.pos[i].y))
                    {
                        continue;
                    }
                    if (mp[next.pos[i].x][next.pos[i].y] == 1)  // 是否需要跳过棋子
                    {
                        next.pos[i].x = next.pos[i].x + dx[j];
                        next.pos[i].y = next.pos[i].y + dy[j];
                    }
                    if (!judge(next.pos[i].x, next.pos[i].y))
                    {
                        continue;
                    }
                    sort(next.pos, next.pos + 4, cmp);
                    int goal = to_num(next);
                    if (vis1[goal])
                    {
                        return true;
                    }
                    if (!vis2[goal])
                    {
                        vis2[goal] = true;
                        q2.push(next);
                    }
                }
            }
        }
    }
    return false;
}

int main()
{
    State start, last;
    while (~scanf("%d%d", &start.pos[0].x, &start.pos[0].y))
    {
        vis1.clear();
        vis2.clear();
        for (int i = 1; i < 4; i++)
        {
            scanf("%d%d", &start.pos[i].x, &start.pos[i].y);
        }
        for (int i = 0; i < 4; i++)
        {
            scanf("%d%d", &last.pos[i].x, &last.pos[i].y);
        }  
        // 每次排好序，否则可能会出现重复遍历
        sort(start.pos, start.pos + 4, cmp);  
        sort(last.pos, last.pos + 4, cmp);
        ans = bfs(start, last);
        printf(ans ? "YES\n" : "NO\n");
    }
    return 0;
}