程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> Seven Puzzle (AOJ 0121 bfs)

Seven Puzzle (AOJ 0121 bfs)

編輯：C++入門知識

Seven Puzzle (AOJ 0121 bfs)

Seven Puzzle

Time Limit : 1 sec, Memory Limit : 65536 KB

Seven Puzzle

7パズルは8つの正方形のカードとこれらのカードがぴたりと収まる枠を使って行います。それぞれのカードは互いに區別できるように、0,1,2....7と番號がつけられています。枠には、縦に2個、橫に4個のカードを並べることができます。

7パズルを始めるときには、まず枠にすべてのカードを入れます。枠のなかで0のカードだけは、上下左右に隣接するカードと位置を交換することができます。たとえば、枠の狀態が図( a )のときに、0のカードの右に隣接した、7のカードと位置を交換すれば、図( b )の狀態になります。あるいは、図( a )の狀態から0のカードの下に隣接した2のカードと位置を交換すれば図( c )の狀態になります。カードの位置を入れ替える操作はこれだけが許されます。図( a )の狀態で0のカードと上下左右に隣接するカードは7と2のカードだけなので、これ以外の位置の入れ替えは許されません。

ゲームの目的は、カードをきれいに整列して図( d )の狀態にすることです。最初の狀態を入力とし、カードをきれいに整列するまでに、必要な最小手數を出力して終了するプログラムを作成してください。ただし、入力されたカードの狀態からは図( d )の狀態に移ることは可能であるとします。

入力データは、1行に8つの數字が與えられます。これらは、最初の狀態のカードの並びを表します。図( a )の數字表現は0,7,3,4,2,5,1,6に、図( c )は2,7,3,4,0,5,1,6となります。

図( a ) 0,7,3,4,2,5,1,6の場合図( b ) 7,0,3,4,2,5,1,6の場合

図( c ) 2,7,3,4,0,5,1,6の場合図( d ) 0,1,2,3,4,5,6,7(最終狀態)

Input

1つ目のパズルの狀態(整數;空白區切り)
2つ目のパズルの狀態(整數;空白區切り)
     :
     :

與えられるパズルの數は1000以下です。

Output

1つ目のパズルの狀態から最終狀態へ移行する最小手數(整數)
2つ目のパズルの狀態から最終狀態へ移行する最小手數(整數)
            :
            :

Sample Input

0 1 2 3 4 5 6 7
1 0 2 3 4 5 6 7
7 6 5 4 3 2 1 0

Output for the Sample Input

0
1
28

題意：給出0~7的序列（2*4），只能0和周圍數字交換，問最少交換多少次可以是給出的序列變成0 1 2 3 4 5 6 7 思路：先搜一遍把所有答案保存下來。

因為一句話位置寫錯了當時沒做出來。。代碼：

#include 
#include 
#include 
#include 
#include 
#include 
#include
#include 
#include 
#include 
#include 
#pragma comment (linker,"/STACK:102400000,102400000")
#define maxn 1005
#define MAXN 2005
#define mod 1000000009
#define INF 0x3f3f3f3f
#define pi acos(-1.0)
#define eps 1e-6
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
#define FRE(i,a,b)  for(i = a; i <= b; i++)
#define FREE(i,a,b) for(i = a; i >= b; i--)
#define FRL(i,a,b)  for(i = a; i < b; i++)
#define FRLL(i,a,b) for(i = a; i > b; i--)
#define mem(t, v)   memset ((t) , v, sizeof(t))
#define sf(n)       scanf("%d", &n)
#define sff(a,b)    scanf("%d %d", &a, &b)
#define sfff(a,b,c) scanf("%d %d %d", &a, &b, &c)
#define pf          printf
#define DBG         pf("Hi\n")
typedef long long ll;
using namespace std;

struct St
{
    int x,y;
    int step;
    int g[2][4];
};

int dir[4][2]={0,1,0,-1,1,0,-1,0};
int mp[2][4];
mapans;
int a[8];

int here(St s)
{
    int i;
    int x=0;
    FRL(i,0,4)
        x=x*10+s.g[0][i];
    FRL(i,0,4)
        x=x*10+s.g[1][i];
    return x;
}

bool ok(St st)
{
    if (st.x>=0&&st.x<2&&st.y>=0&&st.y<4)
        return true;
    return false;
}

void bfs(int sx,int sy)
{
    int i;
    queueQ;
    while (!Q.empty()) Q.pop();
    St st,now;
    st.x=sx;
    st.y=sy;
    st.step=0;
    memcpy(st.g,mp,sizeof(mp));
    ans[here(st)]=0;
    Q.push(st);
    while (!Q.empty())
    {
        st=Q.front();
        Q.pop();
        FRL(i,0,4)
        {
            now.x=st.x+dir[i][0];
            now.y=st.y+dir[i][1];
            if (ok(now))
            {
                memcpy(now.g,st.g,sizeof(st.g));
                swap(now.g[st.x][st.y],now.g[now.x][now.y]);
                int xx=here(now);
                if (!ans[xx])
                {
                    now.step=st.step+1;
                    ans[xx]=now.step;
                    Q.push(now);
                }
            }
        }
    }
}

int main()
{
    int i,j;
    ans.clear();
    FRL(i,0,4)
    mp[0][i]=i;
    FRL(i,0,4)
    mp[1][i]=i+4;
    int sx,sy;
    bfs(0,0);
    while (~scanf("%d",&a[0]))
    {
        FRE(i,1,7)
        sf(a[i]);
        St st;
        FRL(i,0,4)
        st.g[0][i]=a[i];
        FRL(i,0,4)
        st.g[1][i]=a[i+4];
        int xx=here(st);
        pf("%d\n",ans[xx]);
    }
    return 0;
}