[POJ 1198] Solitaire【双向BFS】
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:
本题若用 BFS 求解，状态数高达 (4 * 4)8 = 232，TLE。
所以考虑双向 BFS，将状态数降至 2 * (4 * 4)4 = 217，可以承受（code 中数组只开到 216 也 AC 了）。
采取 hash 判重，以八进制加权，注意 hash 值不应受四个点的顺序影响，可以将四个点先排序。
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;
}
发表评论