题目跳转
HDOJ-1401
题目大意
8*8的棋盘给你四个点的整体的始末状态（貌似不需要一一对应）
移动方式为十字移动，并且在遇到别的棋子的时候，能够一次跳两格。
问是否能在8步之内到达目标位置
思路
双向广搜 - 棋子位置排序 - 哈希
- 双向广搜
- 先采用哪个队列的小，扩展哪个，尽量使得两边的状态数相近。然而只采取这样，会导致一个因为合法状态数过少而使扩展过早Done，使得无法搜出答案。（面向数据是把每个状态的最大步数设为5可过）
- 最后还没搜出答案，再扩展未空的队列。
- 棋子位置排序
- 题目似乎没有明确说明棋子位置是否一一对应。
- 如果不是，让棋子排序，可以使得多个状态化而为一个，大大减小搜取的数据量。
- 哈希
- 观察得，每一位不超过10，转为int后最大的数为88878685，当然采用八进制可以更小，因此采用把点位转为int
- 我一开始采用string，纯纯犯傻了，剩下的变量名s，由此得来（（（
CODE
代码语言：javascript复制#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_posxxxxn";
// 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 << "YESn";
else
cout << "NOn";
}
return 0;
}
