Press "Enter" to skip to content

POJ2965 The Pilots Brothers’ refrigerator

  • 题目链接 POJ2965

  • 题目描述

    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[5][5];
bool flag;
struct node{
    int x,y;
}q[20];

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;
}

Be First to Comment

发表评论

电子邮件地址不会被公开。