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]; map
             
              ans; 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; queue
              
               Q; 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; }

Seven Puzzle (AOJ 0121 bfs)

Seven Puzzle

Seven Puzzle

Input

Output

Sample Input

Output for the Sample Input