﻿HDU 1401 Solitaire(BFS)-Ocrosoft

# Solitaire

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 4161    Accepted Submission(s): 1255

Problem Description
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.

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

Output
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.

Sample Input
```
4 4 4 5 5 4 6 5
2 4 3 3 3 6 4 6

```

Sample Output
```
YES

```

Solution

```#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <conio.h>
#include <cmath>
#include <algorithm>
#include <list>
#include <stack>
#include <string>
#include <vector>
#include <cstring>
#include <cctype>
#include <queue>
#include <set>
#include <climits>
#define ms(a) memset(a,0,sizeof(a))
using namespace std;
int mp[8][8];
int dir[4][2]= {1,0,-1,0,0,1,0,-1};
bool vis[8][8][8][8][8][8][8][8];
struct node
{
int x[4],y[4];
int step;
} sp,ep;
bool check(node p)//判断是否为最终态,1=最终态
{
for(int i=0; i<4; i++)
if(!mp[p.x[i]][p.y[i]])
return 0;
return 1;
}
bool judge(node p,int k)//判断非空,0=非空
{
for(int i=0; i<4; i++)
if(i!=k&&p.x[k]==p.x[i]&&p.y[k]==p.y[i])
return 0;
return 1;
}
bool ncheck(node p)//判断越界和访问，0=未越界，未访问
{
for(int i=0; i<4; i++)
if(p.x[i]<0||p.x[i]>=8||p.y[i]<0||p.y[i]>=8)
return 1;
if(vis[p.x[0]][p.y[0]][p.x[1]][p.y[1]][p.x[2]][p.y[2]][p.x[3]][p.y[3]])
return 1;
return 0;
}
int bfs()
{
node t,tt;
queue<node> q;
sp.step=0;
ms(vis);
vis[sp.x[0]][sp.y[0]][sp.x[1]][sp.y[1]][sp.x[2]][sp.y[2]][sp.x[3]][sp.y[3]]=1;
q.push(sp);
while(!q.empty())
{
t=q.front();
q.pop();
if(t.step>=8)return 0;//这里是结束，不是继续
if(check(t))return 1;
for(int i=0; i<4; i++)
{
for(int j=0; j<4; j++)
{
tt=t,tt.step++;
tt.x[i]+=dir[j][0],tt.y[i]+=dir[j][1];
if(ncheck(tt))continue;//越界或者访问过
if(judge(tt,i))//如果空
{
if(check(tt))return 1;//如果已经是最终态
vis[tt.x[0]][tt.y[0]][tt.x[1]][tt.y[1]][tt.x[2]][tt.y[2]][tt.x[3]][tt.y[3]]=1;
q.push(tt);
}
else//如果非空的
{
tt.x[i]+=dir[j][0],tt.y[i]+=dir[j][1];//再跳一格
if(ncheck(tt)||!judge(tt,i))continue;//还是非空，或者越界
if(check(tt))return 1;//如果已经是最终态
vis[tt.x[0]][tt.y[0]][tt.x[1]][tt.y[1]][tt.x[2]][tt.y[2]][tt.x[3]][tt.y[3]]=1;
q.push(tt);
}
}
}
}
return 0;
}
int main()
{
while(~scanf("%d%d",&sp.x[0],&sp.y[0]))
{
sp.x[0]--,sp.y[0]--;
for(int i=1; i<4; i++)
{
scanf("%d%d",&sp.x[i],&sp.y[i]);
sp.x[i]--,sp.y[i]--;
}
ms(mp);
for(int i=0; i<4; i++)
{
scanf("%d%d",&ep.x[i],&ep.y[i]);
ep.x[i]--,ep.y[i]--;
mp[ep.x[i]][ep.y[i]]=1;
}
printf("%s\n",bfs()?"YES":"NO");
}
return 0;
}
```