HDU
题目链接： Solitaire
大致题意:
在8*8棋盘有四颗棋子，输入开始状态和目标状态的棋子坐标，每次可以移动一个棋子也可以跳过另一个棋子，问能否在8步内走到目标状态
解题思路:
第一种做法：
正常bfs，开一个八维数组
注意：数组大小只能为8，不然会超内存
第二种做法：
双向广搜，8个坐标值位压缩成为10进制作为hash值，并用unordered_set判重，当hash值出现在另一个分支即相遇
剪枝：每个棋子最多只能走4步，因为如果多于4步，那么他们步数之和就会大于8
AC代码:
//第一种方法
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
bool vis[8][8][8][8][8][8][8][8];
int g[10][10];
int fx[][2] = { 1,0,-1,0,0,1,0,-1 };
struct node {int x[4], y[4];int step;
}s, e;
bool check(node a) { //判断是否到终点for (int i = 0; i < 4; ++i) if (!g[a.x[i]][a.y[i]])return 0;return 1;
}
bool judge(node a) { //考虑边界和是否走过for (int i = 0; i < 4; ++i)if (a.x[i] < 0 || a.x[i] >= 8 || a.y[i] < 0 || a.y[i] >= 8)return 1;if (vis[a.x[0]][a.y[0]][a.x[1]][a.y[1]][a.x[2]][a.y[2]][a.x[3]][a.y[3]])return 1;return 0;
}
bool empty(node a, int k) { //判断下一位置是否为空for (int i = 0; i < 4; ++i)if (i != k && a.x[i] == a.x[k] && a.y[i] == a.y[k])return 0;return 1;
}
bool bfs() {memset(vis, 0, sizeof vis);queue<node>q;node a, b;a.step = 0;for (int i = 0; i < 4; ++i) {a.x[i] = s.x[i];a.y[i] = s.y[i];}q.push(a);vis[a.x[0]][a.y[0]][a.x[1]][a.y[1]][a.x[2]][a.y[2]][a.x[3]][a.y[3]] = 1;while (!q.empty()) {a = q.front(); q.pop();if (a.step >= 8)return 0;if (check(a))return 1;for (int i = 0; i < 4; ++i)for (int j = 0; j < 4; ++j) {b = a;b.x[i] += fx[j][0]; b.y[i] += fx[j][1];b.step++;if (judge(b))continue;if (empty(b, i)) { //下一格为空if (check(b))return 1;vis[b.x[0]][b.y[0]][b.x[1]][b.y[1]][b.x[2]][b.y[2]][b.x[3]][b.y[3]] = 1;q.push(b);}else { //不为空，要再走一步b.x[i] += fx[j][0]; b.y[i] += fx[j][1];if (judge(b) || !empty(b, i))continue;if (check(b))return 1;vis[b.x[0]][b.y[0]][b.x[1]][b.y[1]][b.x[2]][b.y[2]][b.x[3]][b.y[3]] = 1;q.push(b);}}}return 0;
}
int main() {while (cin >> s.x[0] >> s.y[0]) {s.x[0]--;s.y[0]--; //必须减1，不然没存会超for (int i = 1; i < 4; ++i) {cin >> s.x[i] >> s.y[i];s.x[i]--;s.y[i]--;}memset(g, 0, sizeof g);for (int i = 0; i < 4; ++i) {cin >> e.x[i] >> e.y[i];e.x[i]--;e.y[i]--;g[e.x[i]][e.y[i]] = 1;}bool flag = bfs();if (flag)cout << "YES" << endl;else cout << "NO" << endl;}return 0;
}
//第二种方法
#include<iostream>
#include<algorithm>
#include<cstring>
#include<unordered_set>
#include<queue>
using namespace std;
int fx[][2] = { 0,1,0,-1,1,0,-1,0 };
struct node {int p[4], step;bool check(int v) {for (int i : p)if (i == v)return 1;return 0;}int hash() {int a[4];memcpy(a, p, sizeof a);sort(a, a + 4);int res = 0;for (int i : a)res = res * 100 + i;return res;}
};
unordered_set<int>st[2];
queue<node>q[2];
void clear() {for (int i = 0; i < 2; ++i) {queue<node>tmp;swap(q[i], tmp);st[i].clear();}
}
bool flag(int i, int hash) { //队列下标和待查hashif (st[i].find(hash) != st[i].end())return 1; //相遇return 0;
}
bool bfs() {while (!q[0].empty() || !q[1].empty()) {for (int i = 0; i < 2; ++i) { //两个队列if (!q[i].empty()) {node tmp = q[i].front(); q[i].pop();tmp.step++;for (int j = 0; j < 4; ++j) { //四个点int x = tmp.p[j] / 10, y = tmp.p[j] % 10;for (int k = 0; k < 4; ++k) { //四个方向int dx = x + fx[k][0], dy = y + fx[k][1];if (dx >= 1 && dx <= 8 && dy >= 1 && dy <= 8 && tmp.check(dx * 10 + dy))dx += fx[k][0], dy += fx[k][1];if (dx >= 1 && dx <= 8 && dy >= 1 && dy <= 8 && !tmp.check(dx * 10 + dy) && tmp.step <= 4) {tmp.p[j] = dx * 10 + dy;if (st[i].find(tmp.hash()) == st[i].end()) {if (flag(!i, tmp.hash()))return 1;q[i].push(tmp); st[i].insert(tmp.hash());}}}tmp.p[j] = x * 10 + y; //回溯}}}}return 0;
}
int main() {while (true) {clear();node tmp; tmp.step = 0;for (int k = 0; k < 2; ++k) {for (int i = 0; i < 4; ++i) {tmp.p[i] = 0;for (int j = 0; j < 2; ++j) {int x; if (scanf("%d", &x) == EOF)exit(0);tmp.p[i] = tmp.p[i] * 10 + x;}}q[k].push(tmp);st[k].insert(tmp.hash());}if (flag(0, q[1].front().hash()) || bfs())cout << "YES" << endl;else cout << "NO" << endl;}return 0;
}
发布评论