加载中...

POJ 2965 - The Pilots Brothers' refrigerator


问题描述

有一冰箱,上面 4x4 共16个开关(- 状态表示 open,+ 状态表 close), 当改变一个开关状态时,该开关所在行、列的全部开关状态也会同时改变。

给出一个开关状态,问从该状态开始,使得所有开关打开(全 -),至少需要操作多少步,并把操作过程打印出来(打印所操作开关的行列坐标,坐标从 1 开始)

解题思路

这题与 POJ-1753 题型类似,有三种解法:

  1. 枚举 + 状态压缩
  2. DFS + 枚举
  3. DFS + 位运算

详见代码注释。

AC 源码

方法一: 枚举 + 状态压缩

/*
    Author:     Exp
    Date:       2017-12-04
    Code:       POJ 2965
    Problem:    The Pilots Brothers' refrigerator
    URL:        http://poj.org/problem?id=2965
*/

/*
    【枚举 + 状态压缩】解题思路:
      这题和 POJ 1753 的解题思路是一模一样的,只是存在几个差异点,使得解题技巧稍微提高了一点.
      没做 POJ 1753 的同学先去做了那题,理解了再回头做这题.

      我这里偷懒,大部分都是直接套用了自己 POJ 1753 的代码,
      因此详细的解题思路就不再复述了(大体思路都是 打表枚举所有状态,然后根据输入的状态查表)

      这里只列出两题的差异,以及针对差异的处理手法(请在已理解并解决POJ 1753的前提下再看):

        ① 最终状态只有全0一种(即所有开关打开), 而POJ-1753是全0或全1均可.
           因此本题只需要枚举从全0状态到达任意状态的过程,无需考虑全1

        ② 反转开关影响的是全列+全行共7个开关,而POJ-1753仅相邻棋子被影响

        ③ 与 POJ-1753 一样,最多只能不重复地操作16次,即同样存在2^16=65536种状态,
           但由于反转单个开关的影响范围改变了,这65536种不重复状态都是不重复的
           (证明略,可BFS列印所有状态得到印证)

        ④ 这题要求输出反转开关的过程,且题目标注为Special Judge(亦即一题多解)

           这是因为操作同样的若干个开关,操作顺序不会影响最终导向的状态, 
           因此反转对象是固定的,反转顺序随意打印,导致了一题多解的存在
           (但由于不存在重复状态,反转次数是固定的)

           在本题同样参考 POJ-1753 的状态压缩方式,即使用 unsigned int 存储开关状态,
           高16位为操作码,低16位为状态码,那么所有操作过的开关都可以从高16位提取,
           而且通过开关在操作码中的二进制位置,可以反向映射到4x4矩阵的行列坐标(行除4,列模4)
*/

#include <iostream>
using namespace std;


// 无符号整型(32位),用于记录开关矩阵编码,主要为了避免int32的负数影响  
// 初始开关矩阵状态为全0(全"-",即open)  
// 高16位为开关矩阵操作位,翻动过的开关位置标记为1  
// 低16位为开关矩阵状态位, 记录当前开关矩阵状态("+"朝上为1:close,"-"朝上为0:open)  
typedef unsigned int _UINT;


const static int MAX_STEP = 16;            // 可反转开关矩阵的最大步数
const static int MAX_STATUS = 65536;    // 总状态数 = 2^16


// 开关矩阵状态掩码:当翻转位置i的开关时,STATUS_MASKS[i]为所有受影响的行列位置 
// 位置i:在4x4开关矩阵内,从左到右、从上到下按0-15依次编码  
const static int STATUS_MASKS[16] = {
    0x0000111F, 0x0000222F, 0x0000444F, 0x0000888F,
    0x000011F1, 0x000022F2, 0x000044F4, 0x000088F8,
    0x00001F11, 0x00002F22, 0x00004F44, 0x00008F88,
    0x0000F111, 0x0000F222, 0x0000F444, 0x0000F888
};


/**
 * 4x4的开关矩阵对象
 */
class SwitchGroup {
    public:
        SwitchGroup();
        ~SwitchGroup();
        void print(int status);        // 打印从全0(open)到指定状态的最小操作步数以及操作过程

    private:
        void bfsAllStatus(void);                // 记录不重复地翻动1-16步可得到的所有开关矩阵状态
        _UINT filp(_UINT _switch, int bitPos);    // 翻动开关矩阵上某个指定位位置的开关

        int toStatus(_UINT _switch);        // 从开关矩阵编码提取状态信息
        int getMaxBitPos(_UINT _switch);    // 从开关矩阵编码提取操作信息,获得其中最大翻转编号的位置
        int getFilpCount(_UINT _switch);    // 从开关矩阵编码提取操作信息,获取从全0状态开始共被翻动开关的次数

    private:
        _UINT* switchs;        // 记录从全0(open)开始到达每个状态的开关矩阵编码
};


int main(void) {
    // 一次计算把所有开关矩阵状态打表
    SwitchGroup* switchGroup = new SwitchGroup();

    // 迭代输入开关矩阵状态 查表
    int switchStatus = 0;
    int byteCnt = 0;
    char byteBuff[5] = { '\0' };
    while(cin >> byteBuff && ++byteCnt) {
        int offset = 4 * (byteCnt - 1);
        for(int i = 0; i < 4; i++) {
            if(byteBuff[i] == '+') {    // -标记为0, +标记为1
                switchStatus |= (0x00000001 << (i + offset));
            }
        }

        // 每输入4个字节求解一次
        if(byteCnt >= 4) {
            switchGroup->print(switchStatus);

            byteCnt = 0;
            switchStatus = 0;
        }
    }
    delete switchGroup;
    return 0;
}


/**
 * 构造函数
 */
SwitchGroup::SwitchGroup() {
    this->switchs = new _UINT[MAX_STATUS];
    memset(switchs, -1, sizeof(_UINT) * MAX_STATUS);

    bfsAllStatus();
}


/**
 * 析构函数
 */
SwitchGroup::~SwitchGroup() {
    delete[] switchs;
    switchs = NULL;
}


/**
 * 初始化不重复地翻动1-16步可得到的所有开关矩阵状态
 *
 *   由于这题所有状态都不重复(状态数达到65536),
 *   相比POJ1753的状态数要多得多(只有4096)。
 *   而且POJ1753可以对无效状态剪枝,而本题由于所有状态都有效,则无法这样剪枝
 *   在这种情况下,不能再像POJ1753那样使用STL的set容器维护BFS队列,
 *   否则会因为set的维护代价过高TLE
 *
 *   因此本题还是切为常规的BFS队列方法搜索所有状态
 *   (理论上是可以根据开关状态对称分布的特性剪枝的,但少了一半搜索,多了一倍运算,提升不明显)
 */
void SwitchGroup::bfsAllStatus(void) {
    const int ALL_OPEN = 0;
    _UINT bfsQueue[MAX_STATUS];        // 初始状态:开关矩阵全open
    int head = 0, tail = 0;
    bfsQueue[tail++] = ALL_OPEN;

    while(head < tail) {
        _UINT lastSwitch = bfsQueue[head++];
        int status = toStatus(lastSwitch);    // 屏蔽高16位操作位,得到低16位的真正开关矩阵状态
        switchs[status] = lastSwitch;        // 保存开关矩阵状态对应的开关矩阵编码

        // 剪枝1:开关是从低位编号开始反转的,为了不重复反转开关,从上一开关矩阵状态的最高位编号开始翻动 
        for(int pos = getMaxBitPos(lastSwitch) + 1; pos < MAX_STEP; pos++) {
            _UINT nextSwitch = filp(lastSwitch, pos);    // 反转开关得到下一个开关矩阵编码
            bfsQueue[tail++] = nextSwitch;
        }
    }
}


/**
 * 反转开关矩阵上某个指定位位置的开关,
 *  此操作会同时改变开关矩阵编码的操作位(高16位)和状态位(低16位)
 * @param _switch 翻转前的开关矩阵编码
 * @param bitPos 要反转的开关位置, 取值范围为[0, 15],
 *                依次对应4x4矩阵上从左到右、自上而下的编号,也对应二进制数从低到高的进制位
 * return 翻转后的开关矩阵编码
 */
_UINT SwitchGroup::filp(_UINT _switch, int bitPos) {
    _UINT OP_MASK = 0x00010000 << bitPos;        // 高16位:当前操作位
    _UINT STATUS_MASK = STATUS_MASKS[bitPos];    // 低16位:相关状态位
    return (_switch ^ (OP_MASK | STATUS_MASK));    // 更新棋盘编码
}


/**
 * 从开关矩阵编码提取开关矩阵状态信息(低16位)
 * return 开关矩阵状态信息
 */
int SwitchGroup::toStatus(_UINT _switch) {
    const _UINT MASK = 0x0000FFFF;
    return (int) (_switch & MASK);
}


/**
 * 从开关矩阵编码提取操作信息(高16位),获得其中最大反转编号的位置
 * @param _switch 开关矩阵编码
 * return 没有操作过则返回-1,否则返回0-15
 */
int SwitchGroup::getMaxBitPos(_UINT _switch) {
    _UINT MASK = 0x80000000;
    int bitPos = -1;
    for(int i = MAX_STEP - 1; i >= 0; i--) {
        if((_switch & MASK) == MASK) {    // 注意加括号, ==优先级比&要高
            bitPos = i;
            break;
        }
        MASK >>= 1;
    }
    return bitPos;
}


/**
 * 从开关矩阵编码提取操作信息(高16位),获取从全0状态开始共被翻动开关的次数
 * @param _switch 开关矩阵编码
 * return 被翻转次数
 */
int SwitchGroup::getFilpCount(_UINT _switch) {
    const _UINT MASK = 0xFFFF0000;
    _switch &= MASK;    // 屏蔽低16位的状态位

    // 判断高16位操作位有多少个1, 即为翻转次数
    int cnt = 0;
    while(_switch > 0) {
        _switch = (_switch & (_switch - 1));
        cnt++;
    }
    return cnt;
}


/**
 * 打印从全0(open)到指定开关矩阵状态的最小操作步数以及操作过程
 * @param status 开关矩阵状态
 * return 最小步数(若不可达则返回-1)
 */
void SwitchGroup::print(int status) {
    if(status >= 0 && status < MAX_STATUS) {
        _UINT _switch = switchs[status];

        // 打印步数
        int step = getFilpCount(_switch);
        cout << step << endl;

        // 打印反转开关过程
        for(int mask = 0x00010000, bit = 0; bit < MAX_STEP; bit++, mask <<= 1) {
            if((_switch & mask) > 0) {
                cout << (bit / 4) + 1 << " " << (bit % 4) + 1 << endl;
            }
        }
    }
}

方法二: DFS + 枚举

需要注意的是:要求输出翻转过程,因此不能用 BFS,必须用 DFS(找到目标后,还要过程回溯)。

POJ 1753 相比,这题还要注意翻棋的方法,若不注意会大大浪费时间导致超时,因为是整行整列翻转,在边界处会出现很多多余操作。

/* DFS + Enum */

//Memory Time 
//240K  641MS 

//本题由于要输出每次翻转的棋子,因此不适宜用BFS,应该使用DFS输出完整路径

#include<iostream>
using namespace std;

bool lock[10][10]={false};
bool flag;
int step;
int ri[16],cj[16];

bool isopen(void)
{
    for(int i=3;i<7;i++)
        for(int j=3;j<7;j++)
            if(lock[i][j]!=true)
                return false;
    return true;
}

void flip(int row,int col)               //其实参考POJ1753的翻棋方法也是可以做出来的,但是会超时不通过
{                                        //超时的原因就是翻棋时有太多多余的操作
    lock[row][col]=!lock[row][col];      //POJ1753使用6x6矩形,多余操作只有周围的“一圈”翻棋!
    for(int i=3;i<=6;i++)                //这里使用10x10矩形,多余操作有“三圈”翻棋!
        lock[i][col]=!lock[i][col];      //其实用位运算就可以只使用4x4矩形,大大降低时间复杂度,根本没有多余操作,但是程序会很复杂,不好看
    for(int j=3;j<=6;j++)
        lock[row][j]=!lock[row][j];
    return;
}

void dfs(int row,int col,int deep)
{
    if(deep==step)
    {
        flag=isopen();
        return;
    }

    if(flag||row==7)return;

    flip(row,col);
    ri[deep]=row;
    cj[deep]=col;

    if(col<6)
        dfs(row,col+1,deep+1);
    else
        dfs(row+1,3,deep+1);

    flip(row,col);
    if(col<6)
        dfs(row,col+1,deep);
    else
        dfs(row+1,3,deep);
    return;
}

int main(void)
{
    char temp;
    int i,j;
    for(i=3;i<7;i++)
        for(j=3;j<7;j++)
        {
            cin>>temp;
            if(temp=='-')
                lock[i][j]=true;
        }

    for(step=0;step<=16;step++)
    {
        dfs(3,3,0);
        if(flag)break;
    }

    cout<<step<<endl;
    for(i=0;i<step;i++)
        cout<<ri[i]-2<<' '<<cj[i]-2<<endl;
    return 0;
}

方法三: DFS + 位运算

/* DFS + Bit */

//Memory Time 
//240K   563MS 

//本题由于要输出每次翻转的棋子,因此不适宜用BFS,应该使用DFS输出完整路径

#include<iostream>
using namespace std;

int chess;        //棋盘状态
int step;
bool flag=false;
int ri[16],cj[16];

bool isopen(void)
{
    if(chess==0xFFFF)
        return true;
    else
        return false;
}

void flip(int bit)
{
    chess=chess^(0x1<<bit);  //对翻转位取反
    int row=bit/4;
    int col=bit%4;
    for(int c=0;c<4;c++)
        chess=chess^(0x1<<(row*4+c));  //对全行取反
    for(int r=0;r<4;r++)
        chess=chess^(0x1<<(r*4+col));  //对全列取反
    return;
}

void dfs(int bit,int deep)
{
    if(deep==step)
    {
        flag=isopen();
        return;
    }

    if(flag||bit>15)return;

    int row=ri[deep]=bit/4;
    int col=cj[deep]=bit%4;

    flip(bit);
    if(col<4)
        dfs(bit+1,deep+1);
    else
        dfs((bit+4)/4*4,deep+1);

    flip(bit);
    if(col<4)
        dfs(bit+1,deep);
    else
        dfs((bit+4)/4*4,deep);
    return;
}

int main(void)
{
    /*Input initial state*/

    char temp;
    int i,j;
    for(i=0;i<4;i++)
        for(j=0;j<4;j++)
        {
            cin>>temp;
            if(temp=='-')
                chess=chess^(0x1<<(i*4+j));
        }

    /*DFS*/

    for(step=0;step<=16;step++)
    {
        dfs(0,0);
        if(flag)
            break;
    }

    cout<<step<<endl;
    for(i=0;i<step;i++)
        cout<<ri[i]+1<<' '<<cj[i]+1<<endl;
    return 0;
}

相关资料


文章作者: EXP
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 EXP !
  目录