HDU 1404 ”Solitaire“ (双向广搜)

HDU 1404 ”Solitaire"

OJ：https://acm.hdu.edu.cn/showproblem.php?pid=1401
题目大意：8 * 8 的棋盘，上面有四个棋子，棋子可以上下左右移动，如果在上下左右移动的时候该位置有一个棋子已经放置，可以跳过这个棋子放在后面，不可以连续跳过两个。给一个初始状态和一个目标状态。是否可以在八步之内让初始状态达到目标状态

输入 每排每两个数字代表一个棋子坐标，每排一共四个坐标

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

输出 YES/NO

YES

思路 :
一、用BFS暴力搜索，问题主要是怎么存储每个状态棋子的位置。每个棋子拥有x,y两个坐标数据，目前还不会使用map，就用思维数组vir[64][64][64][64]来储存，虽然占用的内存有点大
二、用双向广度搜索优化BFS，减少搜索次数。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include <algorithm>
using namespace std;
char virs[64][64][64][64] = { '\0'};//记录正向和反向已经到达的状态
int dir[4][2] = { {-1, 0}, {0, 1}, {1, 0}, {0, -1} };//移动的四个方向
struct node {
	int state[4];
	int step;
};
//检查另一个方向是否到达过，并对当前状态排序
int visited(int* str,char flag) {
	sort(str, str + 4);
	if (!virs[str[0]][str[1]][str[2]][str[3]]) {
		virs[str[0]][str[1]][str[2]][str[3]] = flag;
		return 0;
	}
	if (flag == virs[str[0]][str[1]][str[2]][str[3]]) return 0;
	else return 1;
}
//检查是否可以移动或者跳棋，如果可以移动并返回true
bool is_move(int* str, int i, int n) {
	int x = str[i] % 8;
	int y = str[i] / 8;
	x = x + dir[n][0];
	y = y + dir[n][1];
	if (x < 0 || x >= 8 || y < 0 || y >= 8) return false;
	for (int j = 0; j < 4; j++) {
		if (x + y * 8 == str[j]) {
			x = x + dir[n][0];
			y = y + dir[n][1];
			for (int m = 0; m < 4; m++) {
				if (x + y * 8 == str[m] || x < 0 || x >= 8 || y < 0 || y >= 8) return false;
			}
		}
	}
	str[i] = x + y * 8;
	return true;
}
int start[4];
int goal[4];
//双向bfs
int bfs() {
	memset(virs, '\0', sizeof(virs));
	queue <node> q1, q2;
	node head, next;
	memcpy(head.state, start, sizeof(start));
	head.step = 0;
	if (visited(head.state, '1')) return 1;
	q1.push(head);
	memcpy(head.state, goal, sizeof(goal));
	head.step = 0;
	if (visited(head.state, '2')) return 1;
	q2.push(head);
	while (!q1.empty() || !q2.empty()) {
		if (!q1.empty()) {
			head = q1.front();
			q1.pop();
			if (head.step >= 4) continue;//弹空队列
			for (int i = 0; i < 4; i++) {
				for (int j = 0; j < 4; j++) {
					next = head;
					next.step++;
					if (!is_move(next.state, i, j)) continue;
					if (visited(next.state, '1')) return 1;
					q1.push(next);
				}
			}
		}
		if (!q2.empty()) {
			head = q2.front();
			q2.pop();
			if (head.step >= 4) continue;//弹空队列
			for (int i = 0; i < 4; i++) {
				for (int j = 0; j < 4; j++) {
					next = head;
					next.step++;
					if (!is_move(next.state, i, j)) continue;
					if (visited(next.state, '2')) return 1;
					q2.push(next);
				}
			}
		}
	}
	return 0;
}
int main() {
	int r, c;
	while (~scanf("%d%d", &r, &c)) {
		memset(start, 0, sizeof(start));
		memset(goal, 0, sizeof(goal));
		start[0] = (r - 1) * 8 + (c - 1);
		for (int i = 1; i < 4; i++) {
			scanf("%d%d", &r, &c);
			start[i] = (r - 1) * 8 + (c - 1);
		}
		for (int i = 0; i < 4; i++) {
			scanf("%d%d", &r, &c);
			goal[i] = (r - 1) * 8 + (c - 1);
		}
		int ans = bfs();
		printf("%s\n", ans ? "YES" : "NO");
	}
	
	return 0;
}