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;
}