【POJ 1753】Flip Game

1753

题目简介：

翻转一个4*4的黑白棋矩阵使之全黑或全白，每次翻转会带动周围上下左右四个棋子进行翻转

方法：

状态压缩，广度搜索

解题思路：

1. 状态压缩

   ​ 该棋面上有16个棋子，每个棋子对应黑白两种状态，可以将其看作一个16位的二进制数，1代表白色，2代表黑色的状态，则这幅棋盘的所有状态均可用一个$1-(2^{16}-1)$ 中间的一个数进行表示

2. 翻转操作

   ​ 2.1每次翻转该棋子及其周围上下左右的四个棋子，在而压缩过后，可以看作是原来棋盘对应的一个二进制数与一个固定的，至于编号相关的二进制数进行一次异或操作（^），即可得到新棋盘的状态

   ​ 2.2我们可以预先求出每一个编号及其周围翻转过后的二进制状态备用。

   部分代码

//处理16种翻转状态
int change(){
    for(int i = 0; i<size;i++){
        for(int j = 0; j<size;j++){ //(i*size+j)位该位置的编号
            int value = 1<<(i*size+j);
            for(int m = 0; m <dir_num;m++){
                int next_x = i + dir_x[m];
                int next_y = j + dir_y[m];
                if(Judge(next_x,next_x)) value += 1<<(next_x*size+next_y);
            }
            pos[i*size+j] = value;
        }
    }
}

3. 搜索操作（BFS）

   初始条件是棋盘的初始状态压缩后形成的二进制数

   终止条件是棋盘全黑或全白，对应的状态分别为0， $2^{16}-1$

   首先创建一个队列，初始的info结构体中存储初始状态和步数（此时为0），将其压入栈中；

   取栈顶元素并将其出栈，在现有棋盘状态下通过翻转操作遍历1-16编号的棋子翻转后下一次棋盘的状态，并将这些状态入栈，以此进行循环进行广度优先搜索。

   值得注意的是，每次进行翻转操作后step需要递增，且棋盘状态每次变化，都要用标记数组visit进行标记，防止重复访问。

   附代码：

//广度优先搜索
int BFS(int value){
   queue<info> q;
   info s = {value, 0};
   q.push(s);
   visit[s.value] = 1;
    while (!q.empty()){
        info f = q.front();
        q.pop();
        if(f.value == 0 || f.value == (1<<(size*size))-1)
            return f.step;
        for(int i = 0; i < size*size;i++){
            info next = {f.value^pos[i], f.step+1};
            if(!visit[next.value]){
                q.push(next);
                visit[next.value] = 1;
            }
        }
    }

    return ERROR;    // 无法到达目标状态，返回 -1
}

完整代码：

/*
 * 状态压缩以及BFS搜索s
 */

#include "iostream"
#include "cstdio"
#include "cstring"
#include "queue"
#define OK 1
#define ERROR -1
using namespace std;

int dir_x[4] = {0, 0, -1, 1}; //上下左右的顺序
int dir_y[4] = {1, -1, 0, 0};
const int size = 4;
const int dir_num = 4;
int pos[size*size]; //记录翻转之后的改变值
int visit[1<<(size*size)]; //记录某种状态是否备访问过；
// int数组不能用true false进行标记，只能使用0-1

struct info{
    int value;
    int step;
};

int Judge(int x, int y){ //判断是否在范围里
    if(x >=0 && x <size && y>=0 && y<size) return OK;
    else return ERROR;
}
//处理16种翻转状态
int change(){
    for(int i = 0; i<size;i++){
        for(int j = 0; j<size;j++){ //(i*size+j)位该位置的编号
            int value = 1<<(i*size+j);
            for(int m = 0; m <dir_num;m++){
                int next_x = i + dir_x[m];
                int next_y = j + dir_y[m];
                if(Judge(next_x,next_x)) value += 1<<(next_x*size+next_y);
            }
            pos[i*size+j] = value;
        }
    }
}

//广度优先搜索
int BFS(int value){
   queue<info> q;
   info s = {value, 0};
   q.push(s);
   visit[s.value] = 1;
    while (!q.empty()){
        info f = q.front();
        q.pop();
        if(f.value == 0 || f.value == (1<<(size*size))-1)
            return f.step;
        for(int i = 0; i < size*size;i++){
            info next = {f.value^pos[i], f.step+1};
            if(!visit[next.value]){
                q.push(next);
                visit[next.value] = 1;
            }
        }
    }

    return ERROR;    // 无法到达目标状态，返回 -1
}

int main(){
    change();
    char str[5];
    int value = 0;
    for(int i=0; i<size; ++i) {
        scanf("%s", str);
        // 计算起始状态的值
        for(int j=0; j<size; ++j) {
            if(str[j] == 'w')
                value += 1 << (i*size + j);
        }
    }
    int ans = BFS(value);
    if(ans >= 0) printf("%d\n", ans);
    else printf("Impossible\n");
    return 0;
}