# [POJ 1198] Solitaire【双向BFS】

• 2017-12-31
• 0
• 0

## Problem:

 Time Limit: 5000MS Memory Limit: 65536K Case Time Limit: 1000MS

Description

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.
Write a program that:

• reads two chessboard configurations from the standard input,
• verifies whether the second one is reachable from the first one in at most 8 moves,
• writes the result to the standard output.

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.

Output

The output should contain one word 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`

Source

Southwestern Europe 2002

## Solution:

hash 数组若开到 88 = 16777216，需要空间恰为 65536KB，MLE。可以证明 hash 值不会超过 (8,5)(8,6)(8,7)(8,8) 四个点所构成的 15982527，需要空间 62433.3KB，成功卡住空间限制。

## Code: O(玄学) [62840K, 266MS]

```#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = { 0, 0,-1, 1};

struct Point{
int x, y;

Point() {}
Point(int x, int y): x(x), y(y) {}

inline bool operator < (const Point &p2) const {
if(x == p2.x) return y < p2.y;
return x < p2.x;
}

inline bool operator == (const Point &p2) const {return x == p2.x && y == p2.y;}

inline bool isLegal() {return x > 0 && x <= 8 && y > 0 && y <= 8;}
};

struct State{
Point p[4];
int stp;

inline int getHash(){
sort(p, p + 4);  // The hash value should not be influenced by the order of the points
int hshval = 0;
for(register int i = 0; i < 4; i++){
hshval = hshval * 8 + (p[i].x - 1);
hshval = hshval * 8 + (p[i].y - 1);
}
return hshval;  // The hash value is in [0, 15982527]
}

inline bool isCoincident(int pointId){
for(register int i = 0; i < 4; i++){
if(i == pointId) continue;
if(p[i] == p[pointId]) return 1;
}
return 0;
}  // Test after transferring to check if points are coincident
} s, t;

struct Queue{
State node[65540];
int fr, re;

inline void clear() {fr = re = 0;}

inline bool empty() {return fr == re;}

inline void push(const State &x) {node[re++] = x;}

inline void pop() {fr++;}

inline State front() {return node[fr];}
} q;

int vis[15982530];  // Very close to Memory Limit

inline bool bidirectional_BFS(){
memset(vis, 0, sizeof(vis)), q.clear();
vis[s.getHash()] = 1, q.push(s);
vis[t.getHash()] = 2, q.push(t);
while(!q.empty()){
State u = q.front();
int uHash = u.getHash();
for(register int i = 0; i < 4; i++)
for(register int dir = 0; dir < 4; dir++){
State v = u;
v.p[i].x += dx[dir], v.p[i].y += dy[dir];  // Move
if(!v.p[i].isLegal()) continue;
if(v.isCoincident(i)){
v.p[i].x += dx[dir], v.p[i].y += dy[dir];  // Jump
if(!v.p[i].isLegal() || v.isCoincident(i)) continue;
}
int vHash = v.getHash();
if(!vis[vHash]){
vis[vHash] = vis[uHash];
v.stp = u.stp + 1;
if(v.stp < 4) q.push(v);  // Each 4 steps at most
}
if(vis[vHash] != vis[uHash]) return 1;
}
q.pop();
}
return 0;
}

int main(){
while(scanf("%d%d", &s.p[0].x, &s.p[0].y) != EOF){
for(register int i = 1; i < 4; i++) scanf("%d%d", &s.p[i].x, &s.p[i].y);
for(register int i = 0; i < 4; i++) scanf("%d%d", &t.p[i].x, &t.p[i].y);
sort(s.p, s.p + 4), sort(t.p, t.p + 4);
bool allEqual = 1;
for(register int i = 0; i < 4; i++)
if(!(s.p[i] == t.p[i])){
allEqual = 0;
break;
}
if(allEqual){
puts("YES");
continue;
}  // Special judge for the case of the same origin and destination
s.stp = t.stp = 0;
if(bidirectional_BFS()) puts("YES");
else puts("NO");
}
return 0;
}
```

#### 评论

darkleafin.cf
(该域名已过期且被抢注。。)
darkleafin.github.io

49750

https://github.com/Darkleafin

OPEN AT 2017.12.10

Please refresh the page if the code cannot be displayed normally.

https://visualgo.net/en

- Theme by Qzhai