poj-1753题题解思路

0
12

今天天气很好!

首先题意是这样的::

翻盖游戏是在一个长方形的4×4场上进行的,其16个方格中的每一个都放置了双面的棋子。每一块的一边是白色的,另一边是黑色的,每一块都是躺着的,要么是黑色的,要么是白色的。每一轮你翻转3到5块,从而改变他们的上边的颜色从黑色到白色,反之亦然。每一轮将翻转的棋子按照以下规则进行选择:

    1. 选择16件中的任何一件。
    2. 将选定的部分和所有相邻的部分翻转到左边、右边、顶部和所选部分的底部(如果有的话)。
    3. 以以下立场为例:

      bwbw
      瓦特
      bbwb
      bwwb
      在这里,“b”表示其黑色一侧向上的部分,而“w”表示其白色一侧向上的部分。如果我们选择从第3行翻转第1部分(此选择显示在图片中),则字段将成为:

      bwbw
      bwww
      瓦布
      瓦布
      游戏的目标是翻转所有的棋子,白色的一面向上或所有的碎片黑色的一面向上。您将编写一个程序,该程序将搜索实现此目标所需的最小轮数。

      1. 那么首先我用的是BFS解
      2. 2.判重用康拓展开,把状态转换成排列序号的来

      1. #include<iostream>
        #include<queue>
        #include<cstring>
        using namespace std;
        typedef struct table {
        int pic[6][6];
        }table;

        table start; //初始状态

        int P[16] = { 1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768 };
        bool vis[65536]; //状态数组
        int dist[65536];
        queue<table>Q;
        //黑0 白1
        char Negate(int ch)
        {
        if (ch)
        return 0;
        return 1;
        }

        void turn(int x, int y, table& T)
        {
        T.pic[x][y] = Negate(T.pic[x][y]); //自身
        T.pic[x][y – 1] = Negate(T.pic[x][y – 1]); //左侧
        T.pic[x][y + 1] = Negate(T.pic[x][y + 1]); //右侧
        T.pic[x – 1][y] = Negate(T.pic[x – 1][y]); //上侧
        T.pic[x + 1][y] = Negate(T.pic[x + 1][y]); //下侧
        }

        int get_dec(table T) //位压缩
        {
        int dec = 0;
        int s = 0;
        for (int i = 4; i > 0; –i)
        for (int j = 4; j > 0; –j)
        {
        dec += T.pic[i][j] * P[s];
        s++;
        }
        return dec;
        }

        int BFS()
        {
        Q.push(start); //初始状态入队
        int st = get_dec(start); //获取索引
        vis[st] = true;
        int front = 1, rear = 2;
        table Now;
        while (front < rear)
        {
        Now = Q.front(); //头结点出队
        Q.pop();
        int index = get_dec(Now); //获取索引
        if (index == 0 || index == 65535) //找到终点
        return front;
        for (int i = 0; i < 16; ++i)
        {
        int x = i / 4 + 1; //横坐标
        int y = i % 4 + 1; //纵坐标
        table Next = Now;
        turn(x, y, Next); //变换求下一步
        int ni = get_dec(Next);
        if (!vis[ni])
        {
        vis[ni] = true;
        Q.push(Next);
        dist[rear] = dist[front] + 1;
        rear++;
        }
        }
        front++;
        }
        return -1;
        }

        int main() {
        for (int i = 0; i < 6; ++i)
        for (int j = 0; j < 6; ++j)
        start.pic[i][j] = 0;
        memset(vis, 0, sizeof(vis));
        for (int i = 1; i <= 4; ++i)
        for (int j = 1; j <= 4; ++j)
        {
        char ch;
        cin >> ch;
        if (ch == ‘w’)
        start.pic[i][j] = 0;
        else
        start.pic[i][j] = 1;
        }

        int s = BFS();
        if (s != -1)
        cout << dist[s] << endl;
        else
        cout << “Impossible” << endl;
        return 0;
        }

<

发布回复

请输入评论!
请输入你的名字