文章目录
- 排书
- 回转游戏
一、排书OJ链接
本题思路:先考虑每一步的决策数量：当抽取长度为 i 的一段时，有 n−i+1 种抽法，对于每种抽法，有 n−i 种放法。另外，将某一段向前移动，等价于将跳过的那段向后移动，因此每种移动方式被算了两遍，所以每个状态总共的分支数量是：∑ni=1(n−i)∗(n−i+1)/2=(15∗14+14∗13+…+2∗1)/2=560。考虑在四步以内解决，最多有 5604个状态，会超时。可以使用双向BFS或者IDA*来优化。我们用IDA*来解决此题。
估价函数：
估价函数需要满足：不大于实际步数
在最终状态下，每本书后面的书的编号应该比当前书多1。
每次移动最多会断开三个相连的位置，再重新加入三个相连的位置，因此最多会将3个错误的连接修正，所以如果当前有 tot个连接，那么最少需要 ⌈tot/3⌉次操作。因此当前状态 s的估价函数可以设计成 f(s)=⌈tot/3⌉。如果当前层数加上 f(s)大于迭代加深的层数上限，则直接从当前分支回溯。
#include <bits/stdc++.h>constexpr int N=20;int n;
int q[N], w[5][N];int f()
{int res = 0;for (int i = 0; i + 1 < n; i ++ )if (q[i + 1] != q[i] + 1)res ++ ;return (res + 2) / 3;
}bool check()
{for (int i = 0; i < n; i ++ )if (q[i] != i + 1)return false;return true;
}bool dfs(int depth, int max_depth)
{if (depth + f() > max_depth) return false;if (check()) return true;for (int l = 0; l < n; l ++ )for (int r = l; r < n; r ++ )for (int k = r + 1; k < n; k ++ ){memcpy(w[depth], q, sizeof q);int x, y;for (x = r + 1, y = l; x <= k; x ++, y ++ ) q[y] = w[depth][x];for (x = l; x <= r; x ++, y ++ ) q[y] = w[depth][x];if (dfs(depth + 1, max_depth)) return true;memcpy(q, w[depth], sizeof q);}return false;
}int main()
{std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);int T;std::cin>>T;while (T -- ){std::cin>>n;for (int i = 0; i < n; i ++ ) std::cin>>q[i];int depth = 0;while (depth < 5 && !dfs(0, depth)) depth ++ ;if (depth >= 5) std::cout<<"5 or more"<<std::endl;else std::cout<<depth<<std::endl;}return 0;
}
二、回转游戏OJ链接
本题思路:本题采用 IDA* 算法，即迭代加深的 A* 算法。
估价函数：
统计中间8个方格中出现次数最多的数出现了多少次，记为 k 次。
每次操作会从中间8个方格中移出一个数，再移入一个数，所以最多会减少一个不同的数。
因此估价函数可以设为 8−k。
剪枝：
记录上一次的操作，本次操作避免枚举上一次的逆操作。
如何保证答案的字典序最小？
由于最短操作步数是一定的，因此每一步枚举时先枚举字典序小的操作即可。
时间复杂度假设答案最少需要 k 步，每次需要枚举 7 种不同操作（除了上一步的逆操作），因此最坏情况下需要枚举 7^k种方案。但加入启发函数后，实际枚举到的状态数很少。
#include <bits/stdc++.h>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 = std::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 (std::cin>>q[0],q[0]){for (int i = 1; i < N; i ++ ) std::cin>>q[i];int depth = 0;while (!dfs(0, depth, -1)){depth ++ ;}if (!depth) std::cout<<"No moves needed";for (int i = 0; i < depth; i ++ ) std::cout<<(char)('A' + path[i]);std::cout<<std::endl<< q[6]<<std::endl;}return 0;
}
