2013
12-09

# 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

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

#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
*/

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