- 每行每列的字母必须互不相同。
- 每行每列的数字也必须互不相同。
-
elements存储了所有的元素。 -
rowLetters和colLetters用于记录每行每列的字母使用情况。 -
rowNumbers和colNumbers用于记录每行每列的数字使用情况。 -
used是一个布尔数组，用于标记元素是否已被使用。 -
solutions是一个unordered_set，用来去重并存储符合条件的方阵排列。 -
递归终止条件：如果
row == N，说明矩阵已经填满，将当前排列转为字符串并存储到solutions中。 -
下一步计算：根据当前单元格的位置，计算下一个
row和col。 - 条件检查：确保当前选择的字母和数字没有在对应的行和列中重复。
- 回溯：尝试所有未使用的元素，递归填充下一个单元格。若不符合条件则撤销选择，继续尝试其他元素。
- 本题通过 回溯算法 构建
4x4的正交拉丁方阵。 - 利用条件限制和
used标记来减少重复排列的生成。 - 采用
unordered_set进行去重，保证输出结果的唯一性。
古代王国的正交拉丁方阵秘文题解
题目分析
题目要求我们将 16 个元素（如 "a1", "a2", "a3", …, "d4"）填入 4x4 的矩阵中，使得每一行、每一列中相同的字母和数字都只出现一次。这符合 正交拉丁方阵 的定义。我们需要找到所有满足条件的排列组合，并输出这些矩阵的数量和内容。
解题思路
题目涉及到的关键条件是：
考虑到需要枚举所有可能的排列，并排除不满足条件的情况，这显然是一个排列与约束的组合问题。这里我们使用 回溯算法 来解决。
代码解读
以下是解决问题的步骤和代码说明：
1. 定义矩阵与条件记录器
首先定义用于存储矩阵内容的 grid 以及用于记录字母和数字使用情况的集合：
const int N = 4;
vector<string> elements = {
"a1", "a2", "a3", "a4",
"b1", "b2", "b3", "b4",
"c1", "c2", "c3", "c4",
"d1", "d2", "d3", "d4"
};
vector<vector<string>> grid(N, vector<string>(N)); // 4x4的网格
set<char> rowLetters[N], colLetters[N]; // 记录每行每列使用过的字母
set<char> rowNumbers[N], colNumbers[N]; // 记录每行每列使用过的数字
bool used[16]; // 记录元素是否已使用
unordered_set<string> solutions; // 用于存储所有去重的排列
2. 转换矩阵为字符串
将当前的 4x4 矩阵转换为字符串，方便输出和去重操作：
string gridToString() {
string result = "";
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
result += grid[i][j] + " ";
}
result += "\n";
}
return result;
}
3. 实现回溯函数
回溯函数用于递归地填充矩阵，直到找到所有可能的排列组合：
void backtrack(int row, int col) {
if (row == N) { // 当所有行都填充完时，保存当前排列
solutions.insert(gridToString());
return;
}
int nextRow = (col == N - 1) ? row + 1 : row;
int nextCol = (col == N - 1) ? 0 : col + 1;
for (int i = 0; i < 16; i++) {
if (used[i]) continue;
string element = elements[i];
char letter = element[0];
char number = element[1];
// 检查字母和数字在行列中是否重复
if (rowLetters[row].count(letter) == 0 && colLetters[col].count(letter) == 0 &&
rowNumbers[row].count(number) == 0 && colNumbers[col].count(number) == 0) {
// 放置当前元素
grid[row][col] = element;
rowLetters[row].insert(letter);
colLetters[col].insert(letter);
rowNumbers[row].insert(number);
colNumbers[col].insert(number);
used[i] = true;
// 递归处理下一个单元格
backtrack(nextRow, nextCol);
// 回溯，撤销当前选择
grid[row][col] = "";
rowLetters[row].erase(letter);
colLetters[col].erase(letter);
rowNumbers[row].erase(number);
colNumbers[col].erase(number);
used[i] = false;
}
}
}
4. 主函数与结果输出
主函数调用 backtrack，并输出去重后的所有结果：
int main() {
fill(begin(used), end(used), false); // 初始化 used 数组为 false
backtrack(0, 0); // 从矩阵的左上角开始回溯
// 输出结果数量及内容
cout << solutions.size() << endl;
for (const auto& el : solutions) {
cout << el << endl;
}
return 0;
}
算法复杂度
由于需要生成所有满足条件的排列，时间复杂度较高。但通过条件限制和 used 标记，可以减少不必要的排列计算。另外，使用 unordered_set 可以实现去重，从而避免重复排列的输出。
总结
通过这样的回溯解法，我们能够得到所有满足条件的方阵排列，完成题目的要求。
复制链接
https://www.lxxblog.cfd/index.php/archives/21/
Warning: Undefined array key "HTTP_ACCEPT_LANGUAGE" in /usr/home/LXX123/domains/www.lxxblog.cfd/public_html/usr/themes/Farallon/comments.php on line 4
Deprecated: stripos(): Passing null to parameter #1 ($haystack) of type string is deprecated in /usr/home/LXX123/domains/www.lxxblog.cfd/public_html/usr/themes/Farallon/comments.php on line 4
[...]c4 d3 a2 b1 数据范围无特殊限制。测试用例.zipcode.cppSpecialJudge.cpp题解[...]
[...]题目列表古代王国的正交拉丁方阵秘文破解石碑中的三阶秘阵二进制谜题：中位数的秘密题解列表古代王国的正交拉丁方阵秘文题解破解石碑中的三阶秘阵题解二进制谜题：中位数的秘密题解[...]