POJ 2965 The Pilots Brothers’ Refrigerator

1.原题

Description

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.

Input

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.

Output

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.

Sample Input
-+ - -
- - - -
- - - -
-+ - -

Sample Output

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

2.题意

题目意思就是有一个4×4的方格，然后是要你从里面任意选择出一个格子，然后它自己，以及它所在行，它所在列的所有的位置都变成相反的，比如‘+’变成‘-’，‘-’变成‘+’，然后问你，最少选多少次格子，可以让所有格子都变成‘-’

3.思路

思路的话，很简单了，此题和上面的POJ1753是一个类型的，基本就是照办，就是位运算+队列的压缩存储状态,这里面多了一个，就是要输出每一步，这样的话，就用了数组来存储每次保存的状态，然后递归来输出结果

4.代码

  
#include<iostream>
#include<queue>
#include<cstring>
#include<string>
#include<string.h>
#define M 65535

using namespace std;

struct state
{
    int data;
    int step;
    int pre;
    int pos;
};

int dir[16] = {4383,8751,17487,34959,4593,8946,17652,35064,7953,12066,20292,36744,61713,61986,62532,63624};
queue sList;
int visList[M+1];

state ssList[(1<<16) +1];

void printP(state s) {
    if(s.pre != -1){
        printP(ssList[s.pre]);
        cout<< s.pos / 4 + 1<<" "<<s.pos % 4 + 1<<endl;
    }
}

void getResult(){

    state ss;
    bool op = false;
    while(!sList.empty()){

        ss = sList.front();
        sList.pop();

        if(ss.data == M) {
            cout<<ss.step<<<endl;
            printP(ss);
            break;
        }

        for (int i = 0; i<16;i++) {
            int temp = ss.data ^ dir[15-i];
            if(visList[temp]) continue;
            state sss;
            sss.data = temp;
            sss.step = ss.step + 1;
            sss.pre = ss.data;
            sss.pos = i;
            ssList[sss.data] = sss;
            visList[temp] = 1;
            sList.push(sss);
        }

    }
}

int main(){
    while(!sList.empty()) sList.pop();
    memset(visList,0,sizeof(visList));
    memset(ssList,0,sizeof(ssList));
    state start;
    int data = 0;
    string s;
    for (int i = 0; i < 4; i++) {
        cin>>s;
        const char* map = s.c_str();
        for (int j=0;j<4;j++) {
            if(map[j] == '-')
                data = (data << 1) + 1;
            else 
                data = (data << 1);
        }
    }
    visList[data] = 1;
    start.data = data;
    start.step = 0;
    start.pre = -1;
    sList.push(start);
    ssList[data] = start;
    getResult();

    return 0;
}

  

5.后续

1）其实这道题先开始是TLE的，主要是因为先开始我维护的是一张string的路径，即存储在struct里面的，每次都进行添加每次的行走的路线，不知道是因为string的操作运行时间太长还是其他什么原因，就是会TLE，而且在cmd中显示还会卡壳的。后来用数字的话，速度就快多了。这个还要再看一下。

2）就是这个题先开始用c++的编译器的时候，会报TLE的，但是后来我改成G++的编译器后，就没有TLE了，直接AC。这个原因也要再查一下

3）吐槽一下，这道题花了一个晚上，感觉有点坑爹，但是是自己的第二道位运算，现在感觉位运算了解一些了吧。