题目描述
“飞行员兄弟”这个游戏,需要玩家顺利的打开一个拥有 16
个把手的冰箱。
已知每个把手可以处于以下两种状态之一:打开或关闭。
只有当所有把手都打开时,冰箱才会打开。
把手可以表示为一个 4×4
的矩阵,您可以改变任何一个位置 [i,j]
上把手的状态。
但是,这也会使得第 i
行和第 j
列上的所有把手的状态也随着改变。
请你求出打开冰箱所需的切换把手的次数最小值是多少。
输入格式
输入一共包含四行,每行包含四个把手的初始状态。
符号 + 表示把手处于闭合状态,而符号 - 表示把手处于打开状态。
至少一个手柄的初始状态是关闭的。
输出格式
第一行输出一个整数 N
,表示所需的最小切换把手次数。
接下来 N
行描述切换顺序,每行输出两个整数,代表被切换状态的把手的行号和列号,数字之间用空格隔开。
注意:如果存在多种打开冰箱的方式,则按照优先级整体从上到下,同行从左到右打开。
C++ 代码
#include <iostream> // 引入输入输出流库
#include <cstdio> // 引入C标准输入输出库
#include <cstring> // 引入C字符串处理库
#include <algorithm> // 引入排序算法库,虽然这里并没有用到
#include <vector> // 引入向量库,用于存储动态数组
using namespace std; // 使用标准命名空间
typedef pair<int, int> PII; // 定义一个pair类型,用于表示坐标(x, y)
const int N = 5; // 定义一个常量N,表示冰箱的尺寸为5x5
char g[N][N]; // 定义一个字符数组,用于存储冰箱的状态
vector<PII> ans, tmp; // 定义两个向量,ans用于存储打开冰箱所需的最小切换次数,tmp用于存储每一次操作后的把手状态
void turn_one(int x, int y) // 函数定义:切换把手[x][y]的状态
{
if (g[x][y] == '+') g[x][y] = '-'; // 如果把手是开的,则关上它
else g[x][y] = '+'; // 如果把手是关的,则打开它
}
void turn_all(int x, int y) // 函数定义:切换[x][y]行和列的状态
{
for (int i = 0; i < 4; i++) // 循环切换每一列
{
turn_one(x, i); // 切换行[x]上的列[i]
turn_one(i, y); // 切换列[y]上的行[i]
}
turn_one(x, y); // 切换行[x]和列[y]交汇处的把手
}
void dfs(int x, int y) // 函数定义:深度优先搜索,从坐标(x, y)开始
{
// 如果所有的把手都操作完了,看看冰箱能否打开
if (x == 3 && y == 4) // 判断是否到达冰箱的右下角
{
bool success = true; // 假设我们能打开冰箱
for (int i = 0; i < 4; i++) // 遍历检查每一行
for (int j = 0; j <4; j++) // 遍历检查每一列
if (g[i][j] == '+') // 如果找到一个开启的把手
{
success = false; // 则说明当前状态无法打开冰箱,将success置为false
goto end; // 跳转到end标签处结束本次循环
}
end: // end标签,用于在上述循环中跳转至此处
if (success) // 如果成功打开了冰箱
if (ans.empty() || tmp.size() < ans.size()) // 如果ans为空或者tmp的切换次数比ans少
ans = tmp; // 则将tmp的状态作为最小切换次数存储到ans中
return; // 结束本次函数调用
}
// 如果y出界了,往下一行移动
if (y == 4) x++, y = 0; // 如果y等于4(即到达冰箱的右边界),则将x加1,y重置为0,继续在当前行的下一行进行搜索
// 操作把手(x, y)(即遍历所有与该把手相连的把手,并切换把手状态)
turn_all(x, y); // 将(x, y)位置的把手状态切换,并影响所有与之相连的把手状态
tmp.push_back({ x, y }); // 将操作的把手坐标存储到tmp中,用于后续恢复状态使用
dfs(x, y + 1); // 在下一列继续进行深度优先搜索,寻找更优解
// 恢复现场(将(x, y)位置的把手状态恢复,并删除存储在tmp中的坐标)
tmp.pop_back();
turn_all(x, y);
// 不操作把手(x, y),直接在下一列进行深度优先搜索,寻找更优解
dfs(x, y + 1);
}
int main()
{
for (int i = 0; i < 4; i++) scanf("%s", g[i]); // 从用户输入中读取冰箱的状态
// 从(0, 0)开始深度优先搜索
dfs(0, 0);
cout << ans.size() << endl;//输出大小
for (int i = 0; i < ans.size(); i++)
printf("%d %d\n", ans[i].first + 1, ans[i].second + 1);
return 0;
}