算法
(IDA*, DFS) O(7k)
本题采用 IDA* 算法，即迭代加深的 A* 算法。
估价函数：
- 统计中间8个方格中出现次数最多的数出现了多少次，记为 k 次。
- 每次操作会从中间8个方格中移出一个数，再移入一个数，所以最多会减少一个不同的数。
- 因此估价函数可以设为 8−k。
剪枝：
- 记录上一次的操作，本次操作避免枚举上一次的逆操作。
如何保证答案的字典序最小？
- 由于最短操作步数是一定的，因此每一步枚举时先枚举字典序小的操作即可。
时间复杂度
假设答案最少需要 k 步，每次需要枚举 7 种不同操作（除了上一步的逆操作），因此最坏情况下需要枚举 7k 种方案。但加入启发函数后，实际枚举到的状态数很少。
C++ 代码
/*
0 1
2 3
4 5 6 7 8 9 10
11 12
13 14 15 16 17 18 19
20 21
22 23
*/
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 24;
int q[N];
int op[8][7] = {
{0, 2, 6, 11, 15, 20, 22},
{1, 3, 8, 12, 17, 21, 23},
{10, 9, 8, 7, 6, 5, 4},
{19, 18, 17, 16, 15, 14, 13},
{23, 21, 17, 12, 8, 3, 1},
{22, 20, 15, 11, 6, 2, 0},
{13, 14, 15, 16, 17, 18, 19},
{4, 5, 6, 7, 8, 9, 10}
};
int center[8] = {6, 7, 8, 11, 12, 15, 16, 17};
int opposite[8] = {5, 4, 7, 6, 1, 0, 3, 2};
int path[100];
int f()
{
static int sum[4];
memset(sum, 0, sizeof sum);
for (int i = 0; i < 8; i ++ ) sum[q[center[i]]] ++ ;
int s = 0;
for (int i = 1; i <= 3; i ++ ) s = max(s, sum[i]);
return 8 - s;
}
bool check()
{
for (int i = 1; i < 8; i ++ )
if (q[center[i]] != q[center[0]])
return false;
return true;
}
void operation(int x)
{
int t = q[op[x][0]];
for (int i = 0; i < 6; i ++ ) q[op[x][i]] = q[op[x][i + 1]];
q[op[x][6]] = t;
}
bool dfs(int depth, int max_depth, int last)
{
if (depth + f() > max_depth) return false;
if (check()) return true;
for (int i = 0; i < 8; i ++ )
{
if (opposite[i] == last) continue;
operation(i);
path[depth] = i;
if (dfs(depth + 1, max_depth, i)) return true;
operation(opposite[i]);
}
return false;
}
int main()
{
while (scanf("%d", &q[0]), q[0])
{
for (int i = 1; i < N; i ++ ) scanf("%d", &q[i]);
int depth = 0;
while (!dfs(0, depth, -1))
{
depth ++ ;
}
if (!depth) printf("No moves needed");
for (int i = 0; i < depth; i ++ ) printf("%c", 'A' + path[i]);
printf("\n%d\n", q[6]);
}
return 0;
}
这个 check() 没必要吧, 直接f()估价的收如果返回0就是中间8个都为相同的情况了
有道理
会更快dfs快一点就会快很多
让大家看看我写的丑陋的代码
#include<iostream> using namespace std; const int N = 24; int a[7], b[7], c[7], d[7]; char opc[8]{ 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H' }; int rev_op[8]{ 5, 4, 7, 6, 1, 0, 3, 2 }; char ans[1000]; bool input() { cin >> a[0]; if (!a[0]) return false; cin >> b[0] >> a[1] >> b[1]; for (int& i : c) cin >> i; cin >> a[3] >> b[3]; for (int& i : d) cin >> i; cin >> a[5] >> b[5] >> a[6] >> b[6]; a[2] = c[2], b[2] = c[4]; a[4] = d[2], b[4] = d[4]; return true; } int H() { int cnt[4]{}; ++cnt[a[2]], ++cnt[a[3]], ++cnt[a[4]]; ++cnt[b[2]], ++cnt[b[3]], ++cnt[b[4]]; ++cnt[c[3]], ++cnt[d[3]]; return 8 - max(max(cnt[1], cnt[2]), cnt[3]); } void movement(int op) { int tmp; switch (op) { case 0: tmp = a[0]; for (int i = 0; i < 6; ++i) a[i] = a[i + 1]; a[6] = tmp, c[2] = a[2], d[2] = a[4]; break; case 1: tmp = b[0]; for (int i = 0; i < 6; ++i) b[i] = b[i + 1]; b[6] = tmp, c[4] = b[2], d[4] = b[4]; break; case 2: tmp = c[6]; for (int i = 6; i > 0; --i) c[i] = c[i - 1]; c[0] = tmp, a[2] = c[2], b[2] = c[4]; break; case 3: tmp = d[6]; for (int i = 6; i > 0; --i) d[i] = d[i - 1]; d[0] = tmp, a[4] = d[2], b[4] = d[4]; break; case 4: tmp = b[6]; for (int i = 6; i > 0; --i) b[i] = b[i - 1]; b[0] = tmp, c[4] = b[2], d[4] = b[4]; break; case 5: tmp = a[6]; for (int i = 6; i > 0; --i) a[i] = a[i - 1]; a[0] = tmp, c[2] = a[2], d[2] = a[4]; break; case 6: tmp = d[0]; for (int i = 0; i < 6; ++i) d[i] = d[i + 1]; d[6] = tmp, a[4] = d[2], b[4] = d[4]; break; case 7: tmp = c[0]; for (int i = 0; i < 6; ++i) c[i] = c[i + 1]; c[6] = tmp, a[2] = c[2], b[2] = c[4]; break; } } bool IDA_star(int cur, int pre_op, int limit) { int h = H(); if (h == 0) return true; if (cur + h > limit) return false; for (int i = 0; i < 8; ++i) { if (rev_op[i] == pre_op) continue; ans[cur] = opc[i]; movement(i); if (IDA_star(cur + 1, i, limit)) return true; movement(rev_op[i]); } return false; } void solve() { int limit; for (limit = 0;; ++limit) { if (IDA_star(0, -1, limit)) break; } if (limit) for (int i = 0; i < limit; ++i) cout << ans[i]; else cout << "No moves needed"; cout << '\n'; cout << a[2] << '\n'; } signed main() { while (input()) solve(); return 0; }为甚么这里题解的难度和题目的难度不一样
后来改难度了吧
这题要是简单，就有点过分了
大佬求助，连样例都过不去
#include <cstdio> #include <algorithm> #include <iostream> #include <cstring> #include <cmath> /* 地图: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 */ using namespace std; const int maxn=24; bool flag=0; int a[maxn],tmp[5],rp=0; const int move[maxn][maxn]={//每种操作的序列 {0,2,6,11,15,20,22}, {1,3,8,12,17,21,23}, {10,9,8,7,6,5,4}, {19,18,17,16,15,14,13}, {23,21,17,12,8,3,1}, {22,20,15,11,6,2,0}, {13,14,15,16,17,18,19}, {4,5,6,7,8,9,10} }; const int cent[maxn]={6,7,8,11,12,15,16,17};//中间的格子 const int inv[maxn]={5,4,7,6,1,0,3,2};//逆运算 int ans[maxn*maxn]; inline int f()//估价 { memset(tmp,0,sizeof(tmp)); for(int i=0;i<8;i++)tmp[a[cent[i]]]++;//统计 int num=0; for(int i=1;i<=3;i++)num=max(num,tmp[i]); return (8-num); } inline void modify(int x)//进行操作x { int t=a[move[x][0]]; for(int i=0;i<=5;i++)a[move[x][i]]=a[move[x][i+1]]; a[move[x][6]]=t; } inline void IDA_star(int step,int last,int maxdep) { if(step+f()>maxdep)return;//剪枝 if(f()==0) { flag=1; return; } if(flag)return; for(int i=0;i<8;i++) { if(inv[i]==last)continue;//无意义 modify(i); ans[step]=i;//记录答案 IDA_star(step+1,i,maxdep); modify(inv[i]);//还原 } } int main() { while(scanf("%d",&a[0]) && a[0]) { for(int i=1;i<=23;i++)scanf("%d",&a[i]); flag=0; for(rp=0;;rp++) { IDA_star(0,-1,rp); if(flag)break; } if(!rp)printf("No moves needed\n"); for(int i=0;i<rp;i++)printf("%c",ans[i]+'A'); printf("\n%d\n",a[6]); } return 0; }为什么y总这个代码用java写就不对了
y总好厉害
y总，这题为啥用IDA星，A星不行么？
应该也可以。IDA*一般比A*好写一点。
嗯呢
y总，A*怎么保证输出字典序？？
A*算法求字典序比较麻烦，因为优先队列中是按估价函数排序而非字典序排序，所以除非将步数最小的所有方案全部求出，否则是无法求出字典序的。
嗯呢，那就是最好用IDA*喽！！
对的，本题用IDA*比较好。
yls，sum数组我不加static段错误了，这是为啥啊
我试了一下，上面的代码去掉
static也可以AC啊。刚才是我测试错误例子的时候发生的MLE，当时没交，现在直接交AC了，我也不知道为啥......
调试功能对输入长度有限制，不能超过2000个字符。提交功能没有此限制。