端午节之结束双向BFS的噩梦

发表于 分类于 阅读次数：

这道题WA了好几天了，总是不知道哪里出了问题，后来看了看，到处都是问题. …… 本来想开始复习考试科目的，奈何总是受这道未A的题目的干扰，总算是解决了。

Solitaire

题意

给你棋盘的初始状态和结束状态，问你从初始状态到结束状态能不能只通过不多于八步的移动。

思路

如果是单向BFS，每次移动有16种可能，8步就是$16^8$ ,还是很大的。不过通过剪枝还是能过的。

但是双向BFS，简单写写就过了，前提是你得会啊QWQ

存储状态用的八维数组，找个时间用hash存储状态。

提醒几点我出错的地方。排序的时候忘记加引用，跳完两步之后，可能那个位置本身也有棋子，注意将状态Push进队列的顺序，是在判断完那几个if之后。记得vis要用char或者bool类型，否则会MLE。

本来已经总结了类似的模板，结果看了网上的题解，不断的修改模板，最后又改回了我的原本的模板。兜兜转转，人生如此QWQ。。

不得不说，双向BFS真快啊！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string>
#include <cstring>
#include <queue>
using namespace std;
char vis[8][8][8][8][8][8][8][8];

struct node
{
    int x[4], y[4];
} a, b;
queue<node>Q[2];
int selfsort(node &a)
{
    for(int i = 0; i < 4; ++i)
    {
        for(int j = 0; j < 4; ++j)
        {
            if(a.x[i] > a.x[j] || (a.x[i] == a.x[j] && a.y[i] > a.y[j]))
            {
                swap(a.x[i], a.x[j]);
                swap(a.y[i], a.y[j]);
            }
        }
    }
}
int dir[4][2] = {{0, 1},{0, -1},{1, 0},{-1,0}};
int check(node c)
{
    return vis[c.x[0]][c.x[1]][c.x[2]][c.x[3]][c.y[0]][c.y[1]][c.y[2]][c.y[3]];
}
int bfs(int id)
{
    int sz = Q[id].size();
    while(sz--)
    {
        node p = Q[id].front();
        Q[id].pop();
        for(int i = 0; i < 4; ++i)        //第几个棋子来走
        {
            for(int j = 0; j < 4; ++j)    //这个棋子的走向
            {
                node c = p;
                c.x[i] = p.x[i] + dir[j][0];
                c.y[i] = p.y[i] + dir[j][1];
                int flag = 0;
                for(int k = 0; k < 4; ++k)        //判断会不会跳过去
                {
                    if(p.x[k] == c.x[i] && p.y[k] == c.y[i] && k != i)
                    {
                        c.x[i] += dir[j][0];
                        c.y[i] += dir[j][1];
                        flag = 1;
                        break;
                    }
                }
                int flag1 = 0;
                if(flag)
                for(int k = 0; k < 4; ++k)
                {
                    if(c.x[i] == p.x[k] && c.y[i] == p.y[k])
                    {
                        flag1 = 1;
                        break;
                    }
                }
                if(flag1)  continue;
                if(c.x[i] < 0 || c.x[i] > 7 || c.y[i] < 0 || c.y[i] > 7)
                    continue;
                selfsort(c);
                if(check(c) == id + 1)
                    continue;
                if((id == 0 && check(c) == 2))
                    return 1;
                if((id == 1 && check(c) == 1))
                    return 1;
                vis[c.x[0]][c.x[1]][c.x[2]][c.x[3]][c.y[0]][c.y[1]][c.y[2]][c.y[3]] = id + 1;
                Q[id].push(c);
            }
        }
    }
    return 0;
}
int solve()
{
    while(!Q[0].empty())
        Q[0].pop();
    while(!Q[1].empty())
        Q[1].pop();
    Q[0].push(a);
    Q[1].push(b);
    int step = 0;
    while(!Q[0].empty() || !Q[1].empty())
    {
        int num1 = bfs(0);
        step++;
        if(num1)
          return step;
        int num2 = bfs(1);
        step++;
        if(num2)
            return step;
    }
    return 0;
}
int main()
{
    while(scanf("%d %d %d %d %d %d %d %d",&a.x[0], &a.y[0], &a.x[1], &a.y[1], &a.x[2], &a.y[2], &a.x[3], &a.y[3]) != EOF)
    {
        memset(vis, '0', sizeof(vis));
        scanf("%d %d %d %d %d %d %d %d",&b.x[0], &b.y[0], &b.x[1], &b.y[1], &b.x[2], &b.y[2], &b.x[3], &b.y[3]);
        for(int i = 0; i < 4; ++i)
        {
            a.x[i]--;
            a.y[i]--;
            b.x[i]--;
            b.y[i]--;
        }
        selfsort(a);
        selfsort(b);
        vis[a.x[0]][a.x[1]][a.x[2]][a.x[3]][a.y[0]][a.y[1]][a.y[2]][a.y[3]] = 1;
        vis[b.x[0]][b.x[1]][b.x[2]][b.x[3]][b.y[0]][b.y[1]][b.y[2]][b.y[3]] = 2;
        int s = solve();
        if(s <= 8)
            cout << "YES" << '\n';
        else
            cout << "NO" << '\n';

    }
}