3 条题解
-
2
#include <bits/stdc++.h> using namespace std; typedef short sh; #define st pair<int, sh> #define B first #define e second sh n, m, T; bool a; bool B_W(st a, sh x) { return a.B >> x & 1; } st now, t, res; map<st, bool> vis; queue<pair<st, vector<sh>>> lis; vector<sh> pa; int main() { ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr); cin >> n; m = (n << 1) + 1; now.e = res.e = n; for (sh i = 0; i < n; ++i) now.B += 1 << i, res.B += 1 << i + 1 + n; lis.push({now, pa}), vis[now] = 1; while (!lis.empty()) { now = lis.front().B, pa = lis.front().e; if (now == res) { for (sh i : pa) cout << i + 1 << (++T % 20 ? ' ' : '\n'); break; } lis.pop(), pa.push_back(0), t = now; if (t.e - 2 >= 0 && B_W(t, t.e - 2) && !B_W(t, t.e - 1)) { pa.back() = t.e - 2; t.B -= 1 << t.e - 2, t.B += 1 << t.e, t.e -= 2; if (!vis[t]) lis.push({t, pa}), vis[t] = 1; } else if (t.e - 1 >= 0 && B_W(t, t.e - 1)) { pa.back() = t.e - 1; t.B -= 1 << t.e - 1, t.B += 1 << t.e, --t.e; if (!vis[t]) lis.push({t, pa}), vis[t] = 1; } t = now; if (t.e + 1 < m && !B_W(t, t.e + 1)) { pa.back() = t.e + 1; ++t.e; if (!vis[t]) lis.push({t, pa}), vis[t] = 1; } else if (t.e + 2 < m && !B_W(t, t.e + 2) && B_W(t, t.e + 1)) { pa.back() = t.e + 2; t.e += 2; if (!vis[t]) lis.push({t, pa}), vis[t] = 1; } } return 0; } -
1
#include <bits/stdc++.h> using namespace std; typedef short sh; #define st pair<int, sh> #define B first #define e second sh n, m, T; bool a; bool B_W(st a, sh x) { return a.B >> x & 1; } st now, t, res; map<st, bool> vis; queue<pair<st, vector<sh>>> lis; vector<sh> pa; int main() { ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr); cin >> n; m = (n << 1) + 1; now.e = res.e = n; for (sh i = 0; i < n; ++i) now.B += 1 << i, res.B += 1 << i + 1 + n; lis.push({now, pa}), vis[now] = 1; while (!lis.empty()) { now = lis.front().B, pa = lis.front().e; if (now == res) { for (sh i : pa) cout << i + 1 << (++T % 20 ? ' ' : '\n'); break; } lis.pop(), pa.push_back(0), t = now; if (t.e - 2 >= 0 && B_W(t, t.e - 2) && !B_W(t, t.e - 1)) { pa.back() = t.e - 2; t.B -= 1 << t.e - 2, t.B += 1 << t.e, t.e -= 2; if (!vis[t]) lis.push({t, pa}), vis[t] = 1; } else if (t.e - 1 >= 0 && B_W(t, t.e - 1)) { pa.back() = t.e - 1; t.B -= 1 << t.e - 1, t.B += 1 << t.e, --t.e; if (!vis[t]) lis.push({t, pa}), vis[t] = 1; } t = now; if (t.e + 1 < m && !B_W(t, t.e + 1)) { pa.back() = t.e + 1; ++t.e; if (!vis[t]) lis.push({t, pa}), vis[t] = 1; } else if (t.e + 2 < m && !B_W(t, t.e + 2) && B_W(t, t.e + 1)) { pa.back() = t.e + 2; t.e += 2; if (!vis[t]) lis.push({t, pa}), vis[t] = 1; } } return 0; } -
-3
#include<bits/stdc++.h> #define x first #define y second using namespace std; typedef pair<int,int> pii; bool vis[1 << 20][20]; int n, endp; map<pii,pii> mp; vector<pii> vec; map<pii,int> d;//这种状态下，部署的值，如果值相等，优先使用从 void dfs(pii s,int t){ if(!mp.count(s)) return;//当没有就返回 vec.push_back({s.x,2*n-s.second+1}); dfs(mp[s],t > 5 ? 2 : t + 1); } void print(){ for (int i = 0; i < vec.size(); i ++){ cout << vec[i].y; if((i+1) % 5 == 0){ cout << endl; } else{ cout << " "; } } } void bfs(pii begin){ queue<pii> q; q.push(begin);//将状态还有空格右边有多少个棋子位置放进去 vis[begin.x][begin.y] = true;//当前状态和2进制为空格位置设置已经遍历过 int res = 0; while(!q.empty()){ pii t = q.front(); int s = t.x, x = t.y; q.pop(); if(s == endp && x == n){ dfs(t, 1); reverse(vec.begin(),vec.end()); print(); return; } //空格左边棋子跨过移动到空格 if(x <= 2*n - 2 && x > 0){ if(s >> x + 1 & 1) {//如果左边0还尝试往右边走，那就不让他走 if((s >> x + 1 & 1) ^ (s >> x & 1)){//如果俩不相同 int ts = s ^ (3 << x); int tx = x + 2; if(!vis[ts][tx]){ q.push({ts,tx}); vis[ts][tx] = true; mp[{ts,tx}] = t; } } } } //空格左边棋子移动到空格上 if(x < 2*n){ int tx = x + 1; if(s >> x & 1){ //如果左边0还尝试往右边走，那就不让他走 if(!vis[s][tx]){ q.push({s,tx}); vis[s][tx] = true; mp[{s,tx}] = t;//当前状态是从t转移过来的 } } } //空格右边棋子移动到空格上 if(x > 0){ if((s >> x - 1 & 1) == 0) { int tx = x - 1; if(!vis[s][tx]){ q.push({s,tx}); vis[s][tx] = true; mp[{s,tx}] = t;//当前状态是从t转移过来的 } } } //空格右边棋子跨过移动到空格 if(x >= 2 && x <= 2*n){ if((s >> x - 2 & 1) == 0) { if((s & (1 << x - 1)) ^ (s & (1 << x - 2))){//如果俩不相同 int ts = s ^ (3 << x - 2); int tx = x - 2; if(!vis[ts][tx]){ q.push({ts,tx}); vis[ts][tx] = true; mp[{ts,tx}] = t; } } } } } } int main(){ freopen("chess.in","r",stdin); freopen("chess.out","w",stdout); cin >> n; int s = 0; for (int i = 1; i <= n; i ++){ endp <<= 1; s <<= 1; s += 1; endp += 1; } s <<= n; bfs({s,n}); return 0; } //空格左边棋子移动到空格上 //空格右边棋子移动到空格上 //空格左边棋子跨过移动到空格 //空格右边棋子跨过移动到空格 //111 000 //11 1000 //1101 00 //11010 0 //110 010 //1 01010 // 101010 //01 1010 //0101 10 //010101 //01010 1 //010 011 //0 01011 //00 1011 //0001 11 //000 111
- 1