4 条题解
-
0
注意到2^16 * 4 * 4 * 4 = 4.2e6，无压力A(W)C(A)
代码很简单，看注释即可
#include<bits/stdc++.h> using namespace std; const int N=4,M=7e4+10; struct node{ int a[4][4]; void p(){//条事戴马 for(int i=0;i<4;i++){ for(int j=0;j<4;j++)printf("%d",a[i][j]); printf("\n"); } printf("\n"); } }; node st,ed; int zh(node t){//将4*4表格用二进制压缩为一个0-65535的数 int ans=0,p=1; for(int i=0;i<4;i++){ for(int j=0;j<4;j++){ if(t.a[i][j])ans+=p; p<<=1; } } return ans; } int dis[M];//初始状态到每一种状态的距离 int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};//上右下左 signed main(){ for(int i=0;i<4;i++){ char s[N];scanf("%s",s); for(int j=0;j<4;j++)st.a[i][j]=s[j]-'0'; } for(int i=0;i<4;i++){ char s[N];scanf("%s",s); for(int j=0;j<4;j++)ed.a[i][j]=s[j]-'0'; } queue<pair<node,int>>q;q.push({st,0});//正常宽搜 memset(dis,-1,sizeof(dis));dis[zh(st)]=0; while(q.size()){ node t=q.front().first;int d=q.front().second;q.pop(); for(int i=0;i<4;i++){ for(int j=0;j<4;j++)if(t.a[i][j]){//枚举有玩具的点 for(int k=0;k<4;k++){//枚举移动的方向 int x=i+dx[k],y=j+dy[k]; if(x>=0&&x<=3&&y>=0&&y<=3&&t.a[x][y]==0){//如果未越界且目标位置没有玩具 swap(t.a[x][y],t.a[i][j]);//交换 if(dis[zh(t)]==-1)q.push({t,d+1}),dis[zh(t)]=d+1;//如果没有这种状态，就加入并记录dis swap(t.a[x][y],t.a[i][j]);//交换回来 } } } } if(dis[zh(ed)]!=-1)break;//找到答案了直接结束 } printf("%d\n",dis[zh(ed)]); return 0; } -
0
发现地图仅 ，最多 种状态，于是直接对状态进行 BFS。
利用
std::bitset压位更好实现。AC Code
#include <bits/stdc++.h> struct Martix { constexpr static size_t _convert(int x, int y) { return x*4+y;} std::bitset<16> data; // 包装一层，防止主程序内编码出错（运行时内联，实际 0 开支） void update(int raw, bool status) { data.set(raw, status); } void update(int x, int y, bool status) { data.set(_convert(x, y), status); } bool get(int x, int y) const { return data.test(_convert(x, y)); } // 使用 `std::unordered_map` / `std::unordered_set` 时，`Key` 需要支持 == 函数，这里直接使用 `std::bitset::operator ==()`。 bool operator==(Martix const &rhs) const { return data == rhs.data; } // 隐式转化为 `std::bitset<16>`，用于 `std::hash` operator const std::bitset<16> &() const { return data; } }; // 使用 `std::unordered_map` / `std::unordered_set` 时，`Key` 需要有 `std::hash<Key>` 特化， // 这里 `Martix` 实际是 `std::bitset<16>` 的包装，这里直接使用 `std::bitset<16>` 的 `std::hash` 特化。 template <> struct std::hash<Martix>: public std::hash<std::bitset<16>> {}; constexpr int8_t dxy[][2] = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}}; int main() { Martix source, target; for(Martix *const pmtx: {&source, &target}) { for(int i = 0; i < 16; ++i) { char ch = getchar(); while(ch != '0' && ch != '1') ch = getchar(); pmtx->update(i, ch == '1'); } } std::queue<std::pair<Martix, int>> Q; Q.emplace(source, 0); // 哈希表维护（实际使用数组也可，因为仅 65536 状态） std::unordered_map<Martix, int> mp; mp.emplace(source, 0); while(!Q.empty()) { auto const [mtx, step] = Q.front(); Q.pop(); if(mtx == target) break; for(int i = 0; i < 4; ++i) for(int j = 0; j < 4; ++j) if(mtx.get(i, j)) for(auto const[dx, dy]: dxy) { int const nx = i + dx, ny = j + dy; if(nx < 0 || ny < 0 || nx >= 4 || ny >= 4) continue; if(mtx.get(nx, ny)) continue; Martix newMtx = mtx; newMtx.update(i, j, false), newMtx.update(nx, ny, true); if(mp.emplace(newMtx, step + 1).second) Q.emplace(newMtx, step + 1); } } std::cout << mp[target]; } -
0
https://blog.csdn.net/tenkuo/article/details/153832212
/* 将： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 压缩成： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 的二进制数 对应着 2 的： 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 次方位的 1 那么 6号位 想要往上移动，对应的 2 次方 10 就得 +4 变成 14，对应 2 号位 想要往下移动，对应的 2 次方 10 就得 -4 变成 6，对应 10 号位 想要往左移动，对应的 2 次方 10 就得 +1 变成 11，对应 5 号位 想要往右移动，对应的 2 次方 10 就得 -1 变成 9，对应 7 号位 当然移动前还要看看这些位置有没有玩具，是不是边界 */ #include<bits/stdc++.h> using namespace std; int st, ed; map<int, bool> mp; struct State { int s; // 二进制状态 int k; // 当前移动次数 }; int get_ans() { queue<State> Q; Q.push({st, 0}); // 初始移动次数为 0 mp.clear(); while (!Q.empty()) { State x = Q.front(); Q.pop(); if (mp[x.s]) { continue; } mp[x.s] = 1; if (x.s == ed) { return x.k; } for (int i = 0; i < 16; i ++) if ( (1 << i) & x.s ){ // 找 x.s 状态上有的 1 // ***注意，当前 i 是二进制位上有的 1，也就是上面说的 0 ~ 15 // 要把 0 ~ 15 映射回去，再移动和判断边界 if (i + 4 < 16 && !( (1 << (i + 4)) & x.s ) && i / 4 != 3) { // 当前 1 的正上方有空位（0） 并且 i 代表的位置不在最上面一行 // ***这里的意思是，最上面一行映射的二进制次方 / 4 都为 3 int new_s = x.s ^ (1 << i) ^ (1 << (i + 4)); // 将当前第 i 位的 1 转移到正上方 Q.push({new_s, x.k + 1}); } if (i - 4 >= 0 && !( (1 << (i - 4)) & x.s ) && i / 4 != 0) { // 当前 1 的正下方有空位（0） 并且 i 代表的位置不在最下面一行 // ***这里的意思是，最下面一行映射的二进制次方 / 4 都为 0 int new_s = x.s ^ (1 << i) ^ (1 << (i - 4)); // 将当前第 i 位的 1 转移到正下方 Q.push({new_s, x.k + 1}); } if (i + 1 < 16 && !( (1 << (i + 1)) & x.s ) && i % 4 != 3) { // 当前 1 的左边有空位（0） 并且 i 代表的位置不在最左边一列 // ***这里的意思是，最左边一列映射的二进制次方 % 4 都为 3 int new_s = x.s ^ (1 << i) ^ (1 << (i + 1)); // 将当前第 i 位的 1 转移到左边 Q.push({new_s, x.k + 1}); } if (i - 1 >= 0 && !( (1 << (i - 1)) & x.s ) && i % 4!= 0) { // 当前 1 的右边有空位（0） 并且 i 代表的位置不在最右边一列 // ***这里的意思是，最右边一列映射的二进制次方 % 4 都为 0 int new_s = x.s ^ (1 << i) ^ (1 << (i - 1)); // 将当前第 i 位的 1 转移到右边 Q.push({new_s, x.k + 1}); } } } return 0; // 不可能到这，但还是写一个 } int main () { ios::sync_with_stdio(false); cin.tie(0); st = 0; // 一定要记得初始化！！ for (int i = 1; i <= 4; i ++) { char s[10]; // 需要开大点，不然会有奇怪的错误 cin >> (s + 1); for (int j = 1; j <= 4; j ++) { st = (st << 1) + (s[j] - '0'); // 相当于把现有的都往前移一位，给当前 0 / 1 空出位置 } } ed = 0; // 这里也是 for (int i = 1; i <= 4; i ++) { char s[10]; cin >> (s + 1); for (int j = 1; j <= 4; j ++) { ed = (ed << 1) + (s[j] - '0'); } } cout << get_ans() << "\n"; return 0; } -
0
huangzheng
LV 6
@ 2025-10-8 17:02:30
#include <bits/stdc++.h> using namespace std; struct node { int s, step; node(){} node(int ss=0, int p=0) { s=ss; step=p; } }; int st, ed; bool v[65537]; queue<node> q; int main() { for(int i=1;i<=4;i++)for(int j=1;j<=4;j++) { int x;scanf("%1d", &x); st<<=1; st+=x; } for(int i=1;i<=4;i++)for(int j=1;j<=4;j++) { int x;scanf("%1d", &x); ed<<=1; ed+=x; } q.push(node(st, 0)); memset(v,0,sizeof(v));v[st]=True; while(q.size()) { node no=q.front();q.pop(); if(no.s==ed){printf("%d",no.step);break;} for(int i=0;i<4;i++)for(int j=0;j<4;j++) { if(i+1<4) { bool x=no.s & (1 << (4 * i + j)); bool y=no.s & (1 << (4 * i + 4 + j)); if(x!=y) { node tno=no;tno.step++; tno.s^= (1 << (4 * i + j)); tno.s^= (1 << (4 * i + 4 + j)); if(!v[tno.s]) { v[tno.s]=True; q.push(tno); } } } if(j+1<4) { bool x=no.s & (1 << (4 * i + j)); bool y=no.s & (1 << (4 * i + j + 1)); if(x!=y) { node tno=no;tno.step++; tno.s^= (1 << (4 * i + j)); tno.s^= (1 << (4 * i + j + 1)); if(!v[tno.s]) { v[tno.s]=True; q.push(tno); } } } } } return 0; }
- 1
