整体思路就是用递归遍历每个把手开与不开的状态,这种状态一共有 2^16种,只有数据量小时才适用此暴力算法。在递归的途中用 path 存储当前遍历的一种状态,再与结果数组比大小得出最终结果即可。
#include <iostream>
#include <vector>
using namespace std;
char handles[5][5]; // handles用于存储把手
vector<pair<int, int>> res; // res 为结果
vector<pair<int, int>> path; // path 用于存储递归途中或开或关的把手
void turn(int row, int col) {
for(int i = 1; i < 5; i++) // 把 col 列的开关全部翻转
handles[i][col] = handles[i][col] == '+'? '-' : '+';
for(int j = 1; j < 5; j++) // 把 row 行的开关全部翻转
handles[row][j] = handles[row][j] == '+'? '-' : '+';
handles[row][col] = handles[row][col] == '+'? '-' : '+'; // 上面两次翻转后,handles[row][col] 会变回原样,需要特殊处理再翻一次
}
void dfs(int row, int col) {
if(row == 4 && col == 5) { // 递归到 handles[4][5] 表明递归到了 2^16 种状态中的一种
for(int i = 1; i < 5; i++)
for(int j = 1; j < 5; j++)
if(handles[i][j] == '+')
return; // 如果有闭合的把手直接返回,节省时间
if(path.size() < res.size() || res.empty()) // 若path的大小小于res的大小且handles把手全为关闭状态,则有可能是最终结果。res.empty()是因为res初始大小为0,若不加此条件res将永远不会被赋值
res = path;
return;
}
if(col == 5) {row++, col = 1;} // 防止数组越界,只加一条此防御语句即可
turn(row, col); // 操作把手handles(row, col)
path.push_back(make_pair(row, col));
dfs(row, col + 1);
turn(row, col); // 不操作把手handles(row, col),开两次把手等于没开
path.pop_back();
dfs(row, col + 1);
}
int main() {
for(int i = 1; i < 5; i++)
for(int j = 1; j < 5; j++)
cin >> handles[i][j]; // 为对应上面程序的逻辑,i 与 j 一定是从1开始输入
dfs(1, 1); // 同上,从1,1开始遍历把手
cout << res.size() << endl;
for(int i = 0; i < res.size(); i++)
cout << res[i].first << " " << res[i].second << endl;
return 0;
}