#include #include using namespace std; // 獲取 0 到 sum-1 中 num 個(gè)數(shù)的組合的所有情況 vector> getPossibleList(int num, int sum) { if (num <= 0) { return {{}}; } vector> possibleList; // 枚舉最后一個(gè)元素做遞歸，該元素前面的元素中還需要選出num-1個(gè)來 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; } // 檢查此種操作序列能否獲得正確結(jié)果 bool checkIsAnswer(vector> matrix, const vector& list) { // 依次按list中的操作，計(jì)算操作后的矩陣狀態(tài) for (const auto& it : list) { auto line = it / matrix[0].size(); auto row = it % matrix[0].size(); matrix[line][row]++; // 自身狀態(tài)改變 if (line > 0) { matrix[line - 1][row]++; // 上方格子狀態(tài)改變 } if (line < matrix.size() - 1) { matrix[line + 1][row]++; // 下方格子狀態(tài)改變 } if (row > 0) { matrix[line][row - 1]++; // 左方格子狀態(tài)改變 } if (row < matrix[0].size()) { matrix[line][row + 1]++; // 右方格子狀態(tài)改變 } } // 檢查結(jié)果矩陣中若有奇數(shù)則失敗 for (const auto& i : matrix) { for (const auto& j : i) { if (j % 2 == 1) { return false; } } } return true; } int main() { // 初始化狀態(tài) 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); } } // 如果有解，直接輸出結(jié)果 if (!answerList.empty()) { cout << "最少操作步數(shù)：" << 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; }