hdu-1401-Solitaire

问题描述

纸牌游戏是在8x8的棋盘上进行的游戏。棋盘的行和列的编号分别为1到8，从上到下，从左到右。

板上有四个相同的部分。一键操作允许：

将一块移到一个空的相邻字段（上，下，左或右），

跳过一块相邻的棋子到一个空白字段（上，下，左或右）。

在上面显示的配置中，每件允许进行4次移动。作为示例，让我们考虑放置在第4行第4列中的片段。它可以上移，下移两行，左移一列或右移两列。

编写一个程序，该程序：

从标准输入中读取两个棋盘配置，

验证最多八个动作中第一个棋盘是否可以到达第二个棋盘配置，

将结果写入标准输出。

输入值

两行输入中的每行包含8个由单个空格分隔的整数a1，a2，…，a8，并描述了棋the上棋子的一种配置。整数a2j-1和a2j（1 <= j <= 4）描述一件的位置-分别是行号和列号。处理到文件末尾。

输出量

对于每个测试用例，输出应包含一个单词-如果在第二输入行中描述的配置最多可以在8个动作中到达第一输入行中描述的配置，则为“是”，否则为“否”。

解题思路

这道题是一个标准的双向广搜题目，思路蛮简单的，就标准的两边搜，然后满足条件退出。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#define vis(tail) vis[(int)tail.t[0].x][(int)tail.t[0].y][(int)tail.t[1].x][(int)tail.t[1].y][(int)tail.t[2].x][(int)tail.t[2].y][(int)tail.t[3].x][(int)tail.t[3].y]
using namespace std;
char vis[8][8][8][8][8][8][8][8];
int dx[4]={-1, 0, 0, 1};
int dy[4]={0, -1, 1, 0};
struct node{
	int x, y;
};
struct Node{
	node t[4];
	int step;
}front,tail;
bool comp(node &a, node &b){
	if(a.x == b.x) return a.y < b.y;
	return a.x < b.x;
}
queue < Node > q;
// 0       1       2       3             
// 0 -> 1, 1 -> 2, 2 -> 3, 3 -> 4;
// 8 -> 7, 7 -> 6, 6 -> 5, 5 -> 4;
void bfs(){
	while(!q.empty()){
		front = q.front();q.pop();
		if(front.step > 3){
			printf("NO\n");
			return;
		}
		for(int i = 0; i < 4; i++){
			for(int k = 0; k < 4; k++){
				tail = front;
				tail.t[i].x = tail.t[i].x + dx[k];
				tail.t[i].y = tail.t[i].y + dy[k];
				bool flag = false;
				int cnt = 0;
				while(!flag && cnt <= 1){
					if(tail.t[i].x >= 0 && tail.t[i].x < 8 && tail.t[i].y >= 0 && tail.t[i].y < 8){
						flag = true;
					}
					for(int j = 0; j < 4; j++){
						if(i == j) continue;
						if(tail.t[i].x == tail.t[j].x && tail.t[i].y == tail.t[j].y){
							flag = false;
							break;
						}
					}
					if(!flag && cnt < 1){
						tail.t[i].x = tail.t[i].x + dx[k];
						tail.t[i].y = tail.t[i].y + dy[k];	
					}
					cnt++;
				}		
				//cout<<"tail: "<<tail.t[0].x<<" "<<tail.t[0].y<<" "<<tail.t[1].x<<" "<<tail.t[1].y<<" "<<tail.t[2].x<<" "<<tail.t[2].y<<" "<<tail.t[3].x<<" "<<tail.t[3].y<<endl;
				if(flag){
					sort(tail.t, tail.t + 4, comp);
					if((int)vis(tail) == 0){
						vis(tail) = vis(front);
						tail.step = front.step + 1;
						q.push(tail);
					}else if((int)vis(tail) != (int)vis(front)){
						printf("YES\n");
						return;
					}
				}
			}
		}
	}
}
int main(){
	while(scanf("%d%d", &front.t[0].x, &front.t[0].y) != EOF){
		memset(vis, 0, sizeof(vis));
		while(!q.empty()) q.pop();
		front.t[0].x--;front.t[0].y--;
		for(int i = 1; i < 4; i++){
			scanf("%d%d", &front.t[i].x, &front.t[i].y);front.t[i].x--;front.t[i].y--;
		}
		front.step = 0;
		sort(front.t, front.t + 4, comp);
		vis(front) = 1;
		q.push(front);
		for(int i = 0; i < 4; i++){
			scanf("%d%d", &front.t[i].x, &front.t[i].y);front.t[i].x--;front.t[i].y--;
		}
		front.step = 0;
		sort(front.t, front.t + 4, comp);
		if(vis(front) == 1){
			printf("YES\n");
			continue;
		}
		vis(front) = 2;
		q.push(front);
		bfs();
	}	
}