﻿ POJ2965 The Pilots Brothers' refrigerator - Carlos Press "Enter" to skip to content

• 题目描述

The game “The Pilots Brothers: following the stripy elephant” has a quest where a player needs to open a refrigerator.
There are 16 handles on the refrigerator door. Every handle can be in one of two states: open or closed. The refrigerator is open only when all handles are open. The handles are represented as a matrix 4х4. You can change the state of a handle in any location [i, j] (1 ≤ i, j ≤ 4). However, this also changes states of all handles in row i and all handles in column j.
The task is to determine the minimum number of handle switching necessary to open the refrigerator.

• 输入

The input contains four lines. Each of the four lines contains four characters describing the initial state of appropriate handles. A symbol “+” means that the handle is in closed state, whereas the symbol “−” means “open”. At least one of the handles is initially closed.

• 输出

The first line of the input contains N – the minimum number of switching. The rest N lines describe switching sequence. Each of the lines contains a row number and a column number of the matrix separated by one or more spaces. If there are several solutions, you may give any one of them.

−+−−
−−−−
−−−−
−+−−

6
1 1
1 3
1 4
4 1
4 3
4 4

• 思路

POJ1753 相同，只不过判断状态和翻转不同。

• 代码

#include <iostream>
#include <queue>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstdlib>
#include <set>
using namespace std;

bool mapx;
bool flag;
struct node{
int x,y;
}q;

bool judge()
{
for(int i=0;i<4;i++)
for(int j=0;j<4;j++)
if(mapx[i][j]!=1)
return false;
return true;
}
void flip(int i,int j)
{
for(int w=0;w<4;w++)
{
mapx[i][w]=!mapx[i][w];
mapx[w][j]=!mapx[w][j];
}
mapx[i][j]=!mapx[i][j];
}

void dfs(int i,int j,int depth,int step)
{
if(depth==step)
{
flag=judge();
return;
}
if(flag || i==4)
return;
flip(i,j);
q[depth].x=i+1;
q[depth].y=j+1;
if(j<3)
dfs(i,j+1,depth+1,step);
else
dfs(i+1,0,depth+1,step);
flip(i,j);
if(j<3)
dfs(i,j+1,depth,step);
else
dfs(i+1,0,depth,step);
return;
}

int main()
{
for(int i=0;i<4;i++)
{
string s;
cin>>s;
for(int j=0;j<4;j++)
{
if(s[j]=='+')
mapx[i][j]=0;
else
mapx[i][j]=1;
}
}
int w;
for(w=0;w<=16;w++)
{
dfs(0,0,0,w);
if(flag)
break;
}
if(flag)
{
cout<<w<<endl;
for(int i=0;i<w;i++)
cout<<q[i].x<<" "<<q[i].y<<endl;
}
return 0;
}