首页 > 搜索 > BFS搜索 > HDU 1401 Solitaire-BFS-[解题报告] C++
2013
12-09

HDU 1401 Solitaire-BFS-[解题报告] C++

Solitaire

问题描述 :

Solitaire is a game played on a chessboard 8×8. 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.

输入:

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. Process to the end of file.

输出:

The output should contain one word for each test case – 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.

样例输入:

4 4 4 5 5 4 6 5
2 4 3 3 3 6 4 6

样例输出:

YES

转载请注明出处,谢谢 http://blog.csdn.net/ACM_cxlove?viewmode=contents           by—cxlove

第一次写双向BFS。

双向BFS即是从起点和终点开始搜,如果出现交点,说明目标点可达。这点要求是八步之内到达,每步有16个状态,16^8的复杂度还是很高的,由于是确定了起点和终点的,十分适合双向BFS,即从起点和终点分别开始搜4步,如果出现交点则说明可达。

HASH的时候采用进制压缩,每个坐标范围为0-7可以用三位二进制表示,总共便是24位二进制表示,其中在HASH的时候注意要把坐标排序。一开始直接用flag[1<<24]结果还是MLE了。后来改成map,不是很习惯。

虽然写成了一个BFS,不过中间部分写得很矬。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<cmath>
#include<string>
#include<vector>
#include<algorithm>
#include<map>
#include<set>
#define inf 1<<30
#define LL long long
#define maxn 1<<24
using namespace std;
struct Point{
	int x,y;
	bool check(){
		if(x<8&&x>=0&&y<8&&y>=0)
			return true;
		return false;
	}
};
struct Node{
	Point pos[4];
	int step;
}s,e;
map<int,int>m;
map<int,int>::iterator it;
int way[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
bool cmp(Point n1,Point n2){
	return n1.x!=n2.x?n1.x<n2.x:n1.y<n2.y;
}
int get_hash(Point *tmp){
	int res=0;
	sort(tmp,tmp+4,cmp);
	for(int i=0;i<4;i++){
		res|=(tmp[i].x<<(6*i));
		res|=(tmp[i].y<<(6*i+3));
	}
	return res;
}
bool bfs(int kind,Node u){
	Node v;
	queue<Node>que;
	u.step=0;
	if(kind==2){
		it=m.find(get_hash(u.pos));
		if(it!=m.end())
			return true;
	}
	m[get_hash(u.pos)]=kind;
	que.push(u);
	while(!que.empty()){
		u=que.front();
		que.pop();
		if(u.step>=4)
			continue;
		for(int i=0;i<4;i++){				
			for(int j=0;j<4;j++){
				v=u;v.step++;
				v.pos[j].x+=way[i][0];
				v.pos[j].y+=way[i][1];			
				int k;
				if(!v.pos[j].check())
					continue;
				for(k=0;k<4;k++)
					if(k!=j&&v.pos[k].x==v.pos[j].x&&v.pos[k].y==v.pos[j].y)
						break;
				if(k==4){
					int HASH=get_hash(v.pos);
					it=m.find(HASH);
					if(kind==1){			
						if(it==m.end()){
							m[HASH]=1;
							que.push(v);
						}
					}
					else{
						if(it==m.end()){
							m[HASH]=2;
							que.push(v);
						}
						else if((*it).second==1)
							return true;
					}
				}
				else{
					v.pos[j].x+=way[i][0];
					v.pos[j].y+=way[i][1];
					if(!v.pos[j].check())
						continue;
					for(k=0;k<4;k++)
						if(k!=j&&v.pos[k].x==v.pos[j].x&&v.pos[k].y==v.pos[j].y)
							break;
					if(k==4){
						int HASH=get_hash(v.pos);
						it=m.find(HASH);
						if(kind==1){
							if(it==m.end()){
								m[HASH]=1;
								que.push(v);
							}
						}
						else{
							if(it==m.end()){
								m[HASH]=2;
								que.push(v);
							}
							else if((*it).second==1)
								return true;
						}
					}
				}
			}
		}
	}
	return false;
}
int main(){
	while(scanf("%d%d",&s.pos[0].x,&s.pos[0].y)!=EOF){
		m.clear();
		for(int i=1;i<4;i++)
			scanf("%d%d",&s.pos[i].x,&s.pos[i].y);
		for(int i=0;i<4;i++)
			scanf("%d%d",&e.pos[i].x,&e.pos[i].y);
		for(int i=0;i<4;i++){
			s.pos[i].x--;s.pos[i].y--;
			e.pos[i].x--;e.pos[i].y--;
		}
		bfs(1,s);
		printf("%s\n",bfs(2,e)?"YES":"NO");
	}
	return 0;
}
/*
2 1 8 8 7 8 1 1
1 5 8 7 7 7 2 4

6 5 5 7 5 1 7 1
7 7 6 5 5 7 6 3

4 6 5 6 5 5 5 2
2 2 7 6 5 3 5 2

4 4 5 5 3 4 7 2
2 7 7 2 6 5 4 8

4 2 3 4 5 5 6 6
2 7 4 4 3 5 4 5

3 3 5 3 6 2 6 6
6 3 8 3 6 6 6 8

3 2 5 3 6 2 6 6
6 3 8 3 6 6 6 8

3 4 4 5 5 5 7 5
3 3 4 3 5 3 6 3
*/

 

解题报告转自:http://blog.csdn.net/acm_cxlove/article/details/7753440


  1. 你的理解应该是:即使主持人拿走一个箱子对结果没有影响。这样想,主持人拿走的箱子只是没有影响到你初始选择的那个箱子中有奖品的概率,但是改变了其余两个箱子的概率分布。由 1/3,1/3 变成了 0, 2/3