POJ 2046 Gap（bfs+状态压缩+map）

比眉伴天荒 2022-06-09 02:07 180阅读 0赞

Let's play a card game called Gap.  
You have 28 cards labeled with two-digit numbers. The first digit (from 1 to 4) represents the suit of the card, and the second digit (from 1 to 7) represents the value of the card.  
  
First, you shu2e the cards and lay them face up on the table in four rows of seven cards, leaving a space of one card at the extreme left of each row. The following shows an example of initial layout.  
![49533c7720baec4308dcd5d1e30fb034_v_1503286279][]  
Next, you remove all cards of value 1, and put them in the open space at the left end of the rows: "11" to the top row, "21" to the next, and so on.  
  
Now you have 28 cards and four spaces, called gaps, in four rows and eight columns. You start moving cards from this layout.  
![be583f260a6daf8ae975cd138006cdac_v_1503286279][]  
At each move, you choose one of the four gaps and fill it with the successor of the left neighbor of the gap. The successor of a card is the next card in the same suit, when it exists. For instance the successor of "42" is "43", and "27" has no successor.  
  
In the above layout, you can move "43" to the gap at the right of "42", or "36" to the gap at the right of "35". If you move "43", a new gap is generated to the right of "16". You cannot move any card to the right of a card of value 7, nor to the right of a gap.  
  
The goal of the game is, by choosing clever moves, to make four ascending sequences of the same suit, as follows.  
![8fbbd9102da6cdd560d5df54f7b6c6b0_v_1503286279][]  
Your task is to find the minimum number of moves to reach the goal layout.

Input

The input starts with a line containing the number of initial layouts that follow.  
  
Each layout consists of five lines - a blank line and four lines which represent initial layouts of four rows. Each row has seven two-digit numbers which correspond to the cards.

Output

For each initial layout, produce a line with the minimum number of moves to reach the goal layout. Note that this number should not include the initial four moves of the cards of value 1. If there is no move sequence from the initial layout to the goal layout, produce "-1".

Sample Input

4
    
    12 13 14 15 16 17 21
    22 23 24 25 26 27 31
    32 33 34 35 36 37 41
    42 43 44 45 46 47 11
    
    26 31 13 44 21 24 42
    17 45 23 25 41 36 11
    46 34 14 12 37 32 47
    16 43 27 35 22 33 15
    
    17 12 16 13 15 14 11
    27 22 26 23 25 24 21
    37 32 36 33 35 34 31
    47 42 46 43 45 44 41
    
    27 14 22 35 32 46 33
    13 17 36 24 44 21 15
    43 16 45 47 23 11 26
    25 37 41 34 42 12 31

Sample Output

0
    33
    60
    -1

题解：

题意：

给你一个28数字的矩阵，一开始你要把11,21,31,41放在每一行的第一个，然后就会有4个缝隙，每次你可以将缝隙左边的数字的后一个数字（比如左边是14，你可以把15）加到缝隙中，然后又会产生新的缝隙。。。。一直循环直到达到一个有序的矩阵，问你最少要操作多少次，第一次不算，不能得到就输出-1

思路：

用bfs模拟整个过程就好了，这里涉及状态的判重，由于开不了那么大的数组，我们可以用哈希做，也可以选择map long long对int的键值对来判断该状态有没有搜索过，当然这里涉及状态压缩位运算，可以用一个数组保存下要求的状态，然后比较当前节点状态就好了

代码：

#include<iostream>
    #include<cstring>
    #include<stdio.h>
    #include<math.h>
    #include<string>
    #include<stdio.h>
    #include<algorithm>
    #include<queue>
    #include<stack>
    #include<map>
    #include<vector>
    #include<deque>
    using namespace std;
    #define lson k*2
    #define rson k*2+1
    #define INF 100861111
    #define ll long long
    #define eps 1e-15
    struct node
    {
        int p[4][8],step;
    };
    int b[4][8]={
    { 11,12,13,14,15,16,17,0},
    { 21,22,23,24,25,26,27,0},
    { 31,32,33,34,35,36,37,0},
    { 41,42,43,44,45,46,47,0}
    };//要获得的矩阵
    map<ll,int>M;
    queue<node>q;
    int main()
    {
        int i,j,n,m,k,test,tag,flag,t,num,x,y;
        node now,next;
        ll d;
        scanf("%d",&test);
        while(test--)
        {
            M.clear();
            while(!q.empty())q.pop();
            for(i=0;i<4;i++)
            {
                now.p[i][0]=0;
                for(j=1;j<8;j++)
                {
                    scanf("%d",&now.p[i][j]);
                }
            }
            for(i=0;i<4;i++)//特殊处理第一步，将11,21,31,41提前
            {
                for(j=1;j<8;j++)
                {
                    if(now.p[i][j]==11||now.p[i][j]==21||now.p[i][j]==31||now.p[i][j]==41)
                    {
                        t=now.p[i][j];
                        now.p[i][j]=0;
                        if(t==11)
                        {
                            now.p[0][0]=11;
                        }
                        else if(t==21)
                        {
                            now.p[1][0]=21;
                        }
                        else if(t==31)
                        {
                            now.p[2][0]=31;
                        }
                        else
                        {
                            now.p[3][0]=41;
                        }
                    }
                }
            }
            now.step=0;
            flag=0;
            q.push(now);//进行bfs
            while(!q.empty())
            {
                now=q.front();
                q.pop();
                tag=1;
                for(i=0;i<4;i++)//检查是否是要求状态
                {
                    for(j=0;j<8;j++)
                    {
                        if(now.p[i][j]!=b[i][j])
                        {
                            tag=0;
                            break;
                        }
                    }
                    if(!tag)
                        break;
                }
                if(tag)
                {
                    flag=1;
                    printf("%d\n",now.step);
                    break;
                }
                for(i=0;i<4;i++)
                {
                    for(j=0;j<8;j++)
                    {
                        if(!now.p[i][j])//搜索0的位置
                        {
                            if(now.p[i][j-1]&&now.p[i][j-1]%10<7)//记录要放在0的位置上的数
                                num=now.p[i][j-1]+1;
                            else
                                continue;
                            for(x=0;x<4;x++)//查找要放的数，更新状态
                            {
                                for(y=0;y<8;y++)
                                {
                                    if(now.p[x][y]==num)
                                    {
                                        next=now;
                                        next.p[x][y]=0;
                                        next.p[i][j]=num;
                                        next.step++;
                                        d=0;
                                        for(n=0;n<4;n++)
                                        {
                                            for(m=0;m<8;m++)
                                            {
                                                d+=next.p[n][m]*(1ll<<(n*10+m));//位运算压缩状态
                                            }
                                        }
                                        if(!M[d])//没有遍历过该状态就加入搜索
                                        {
                                            q.push(next);
                                            M[d]=1;
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
            if(!flag)
            {
                printf("-1\n");
            }
        }
        return 0;
    }

[49533c7720baec4308dcd5d1e30fb034_v_1503286279]: https://odzkskevi.qnssl.com/49533c7720baec4308dcd5d1e30fb034?v=1503286279
[be583f260a6daf8ae975cd138006cdac_v_1503286279]: https://odzkskevi.qnssl.com/be583f260a6daf8ae975cd138006cdac?v=1503286279
[8fbbd9102da6cdd560d5df54f7b6c6b0_v_1503286279]: https://odzkskevi.qnssl.com/8fbbd9102da6cdd560d5df54f7b6c6b0?v=1503286279