当红月落幕之后 第三章 翻地格最优c++源码算法

#include #include using namespace std; // 获取 0 到 sum-1 中 num 个数的组合的所有情况 vector> getPossibleList(int num, int sum) { if (num <= 0) { return {{}}; } vector> possibleList; // 枚举最后一个元素做递归，该元素前面的元素中还需要选出num-1个来 for (int i = num - 1; i < sum; i++) { auto tempList = getPossibleList(num - 1, i - 1); for (auto it : tempList) { it.push_back(i); possibleList.push_back(it); } } return possibleList; } // 检查此种操作序列能否获得正确结果 bool checkIsAnswer(vector> matrix, const vector& list) { // 依次按list中的操作，计算操作后的矩阵状态 for (const auto& it : list) { auto line = it / matrix[0].size(); auto row = it % matrix[0].size(); matrix[line][row]++; // 自身状态改变 if (line > 0) { matrix[line - 1][row]++; // 上方格子状态改变 } if (line < matrix.size() - 1) { matrix[line + 1][row]++; // 下方格子状态改变 } if (row > 0) { matrix[line][row - 1]++; // 左方格子状态改变 } if (row < matrix[0].size()) { matrix[line][row + 1]++; // 右方格子状态改变 } } // 检查结果矩阵中若有奇数则失败 for (const auto& i : matrix) { for (const auto& j : i) { if (j % 2 == 1) { return false; } } } return true; } int main() { // 初始化状态 vector> matrix{ {1, 0, 0}, {1, 1, 0}, {1, 1, 1}, }; // 从操作一次开始，依次搜索操作i次是否能解决 for (int i = 1; i < matrix.size() * matrix[0].size(); i++) { // 获取操作i次的不同操作的组合的集合 auto possibleList = getPossibleList(i, matrix.size() * matrix[0].size()); vector> answerList; // 保存可行的操作集合 for (const auto& it : possibleList) { // 如果操作能使得问题解决，放到可行操作列表中 if (checkIsAnswer(matrix, it)) { answerList.push_back(it); } } // 如果有解，直接输出结果 if (!answerList.empty()) { cout << "最少操作步数：" << i << endl; cout << "可行解法：" << endl; for (auto answer : answerList) { for (auto it : answer) { cout << "{" << it / matrix[0].size() << ", " << it % matrix[0].size() << "} "; } cout << endl; } return 0; } } cout << "无解" << endl; return 0; }