题目链接
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1505
题意 一个8 * 8 的棋盘上面有四个棋子
棋子可以上下左右移动，如果隔壁有个棋子 那就可以跳一步，只能跳一步。
给出 初始状态，和末尾状态 求能不能在8步之内达到
思路
如果是单向BFS (4 * 4)^ 8 = 2 ^ 32 个状态数
太大了
采用双向广搜
状态数 就是
(4 * 4)^ 4 * 2 = 2 ^ 17
因为内存只有32mb
然后我想 用八进制的数字 来存状态
然后转化成十进制
就是 8 ** 8 = 16777216
16777216 * 4 / 1024 = 65536kb = 64mb
爆内存了。。
然后后来想想，既然用了双向广搜来减少时间复杂度了，，不如直接用map 标记 也只是增加了log 的时间复杂度
就试试了。。
对了 那个状态 对四个棋子的位置 一定要排序后再转值 不然可能两个状态是一样的 但是得到的值确实不一样的
然后就A了。
AC代码
#pragma comment(linker, "/STACK:102400000,102400000") #include <cstdio> #include <cstring> #include <ctype.h> #include <cstdlib> #include <cmath> #include <climits> #include <ctime> #include <iostream> #include <algorithm> #include <deque> #include <vector> #include <queue> #include <string> #include <map> #include <stack> #include <set> #include <list> #include <numeric> #include <sstream> #include <iomanip> #include <limits> #define CLR(a, b) memset(a, (b), sizeof(a)); #define pb push_back #define bug puts("***bug***"); #define fi first #define se second #define L(on) ((on)<<1) #define R(on) (L(on) | 1) #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define syn_close ios::sync_with_stdio(false); cin.tie(0); #define sp system("pause"); //#define gets gets_s using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; typedef long double ld; typedef pair <int, int> pii; typedef pair <ll, ll> pll; typedef pair <string, int> psi; typedef pair <string, string> pss; typedef pair <double, int> pdi; const double PI = acos(-1.0); const double EI = exp(1.0); const double eps = 1e-8; const int INF = 0x3f3f3f3f; const ll INFLL = 0x3f3f3f3f3f3f3f3fll; const int maxn = (int)4e3 + 10; const int MAXN = (int)1e2 + 10; const int MOD = (int)1e9 + 7; int readint() { int num; scanf("%d", &num); return num - 1; } struct node { pii G[4]; int step, value, vis; bool operator == (const node& r)const { for (int i = 0; i < 8; i++) if (r.G[i] != G[i]) return false; return true; } void tran() { value = 0; sort(G, G + 4, [](pii a, pii b) { if (a.fi == b.fi) return a.se < b.se; else return a.fi < b.fi; }); for (int i = 0; i < 4; i++) value = value * 10 + G[i].fi, value = value * 10 + G[i].se; } void read(int l, int r) { for (int i = l; i < r; i++) { G[i].fi = readint(); G[i].se = readint();} step = 0; tran(); } }st, tar; void init() { st.G[0].se = readint(); st.G[0].fi--; st.read(1, 4); tar.read(0, 4); st.vis = 0; tar.vis = 1; } int Move[2][4][2] = { -1, 0, 1, 0, 0,-1, 0, 1, -2, 0, 2, 0, 0,-2, 0, 2, }; bool ok(int x, int y) { if (x < 0 || x >= 8 || y < 0 || y >= 8) return false; return true; } void bfs() { if (st == tar) { puts("YES"); return; } queue <node> q[2]; q[0].push(st); q[1].push(tar); map <int, pii> mp[2]; mp[0][st.value] = pii(1, 0); mp[1][tar.value] = pii(1, 0); while (!q[0].empty() && !q[1].empty()) { node u; if (q[0].size() < q[1].size()) { u = q[0].front(); q[0].pop(); } else { u = q[1].front(); q[1].pop(); } if (u.step >= 8) continue; map <pii, int> visit; for (int i = 0; i < 4; i++) visit[u.G[i]] = 1; for (int i = 0; i < 4; i++) { int x = u.G[i].fi, y = u.G[i].se; for (int j = 0; j < 4; j++) { int nx = x + Move[0][j][0]; int ny = y + Move[0][j][1]; if (ok(nx, ny)) { if (visit[pii(nx, ny)]) { nx = x + Move[1][j][0]; ny = y + Move[1][j][1]; if (ok(nx, ny) && visit[pii(nx, ny)] == 0) { node v = u; swap(v.G[i].fi, nx); swap(v.G[i].se, ny); v.step++; v.tran(); if (mp[v.vis][v.value].fi == 0) { mp[v.vis][v.value] = pii(1, v.step); pii tmp = mp[v.vis ^ 1][v.value]; if (tmp.fi == 1 && tmp.se + v.step <= 8) { puts("YES"); return; } q[v.vis].push(v); } } } else { node v = u; swap(v.G[i].fi, nx); swap(v.G[i].se, ny); v.step++; v.tran(); if (mp[v.vis][v.value].fi == 0) { mp[v.vis][v.value] = pii(1, v.step); pii tmp = mp[v.vis ^ 1][v.value]; if (tmp.fi == 1 && tmp.se + v.step <= 8) { puts("YES"); return; } q[v.vis].push(v); } } } } } } puts("NO"); return; } int main() { while (scanf("%d", &st.G[0].fi) != EOF) { init(); bfs(); } }转载于:https://www.cnblogs.com/Dup4/p/9433066.html
