[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:

本题若用 BFS 求解,状态数高达 (4 * 4)8 = 232TLE
所以考虑双向 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;
}

 

 

评论

还没有任何评论,你来说两句吧



常年不在线的QQ:
49750

不定期更新的GitHub:
https://github.com/Darkleafin


OPEN AT 2017.12.10

如遇到代码不能正常显示的情况,请刷新页面。
If the code cannot be displayed normally, please refresh the page.


发现一个优美的网站:
https://visualgo.net/en
















- Theme by Qzhai