下面是一本通OJ上题目和代码
·例一：
题目描述：
在一个4*4的棋盘上有8个黑棋和8个白棋，当且仅当两个格子有公共边，这两个格子上的棋是相邻的。移动棋子的规则是交换相邻两个棋子。
给出一个初始棋盘和一个最终棋盘，请找出一个最短的移动序列使初始棋盘变为最终棋盘。
代码实现：
1 #include<iostream> 2 #include<queue> 3 #define FOR(a,b,c) for(int a=(b);a<(c);a++) 4 using namespace std; 5 6 const int maxn = 16; 7 struct Node{ // 结构体存棋盘的二进制序列和步数 8 int num,d; 9 }; 10 int A,B; 11 int vis[100000]; 12 13 void BFS() { 14 queue<Node> q; 15 q.push((Node){A,0}); 16 while(!q.empty()) 17 { 18 Node u=q.front(); q.pop(); 19 int tmp=u.num; 20 if(tmp==B) { cout<<u.d; return ; } 21 for(int i=15;i>=0;i--) // 棋盘对应的二进制序列，从高到低依次枚举每个位置 22 { 23 int x=(15-i)/4,y=(15-i)%4,w=1<<i,z; //计算该位置在棋盘上的x和y坐标值 24 if(y<3 && (tmp&(1<<i))!=(tmp&(1<<i-1))) //向右交换，二进制序列的i和i-1交换 25 { 26 z=1<<i-1; 27 if(!vis[tmp^z^w]) { 28 vis[tmp^z^w]=1; 29 q.push((Node){tmp^z^w,u.d+1}); 30 } 31 } 32 if(x<3 && (tmp&(1<<i))!=(tmp&(1<<i-4))) //向下交换，二进制序列的i和i-4交换 33 { 34 z=1<<i-4; 35 if(!vis[tmp^z^w]) { 36 vis[tmp^z^w]=1; 37 q.push((Node){tmp^z^w,u.d+1}); 38 } 39 } 40 } 41 } 42 } 43 44 int main() 45 { 46 char c; 47 for(int i=15;i>=0;i--) { 48 cin>>c; 49 if(c!='0') A += 1<<i; 50 } 51 for(int i=15;i>=0;i--) { 52 cin>>c; 53 if(c!='0') B += 1<<i; 54 } 55 if(A==B) cout<<0; 56 else BFS(); 57 }
·例二：
题目描述：
原题来自：HAOI 2008
在一个 4×4 的方框内摆放了若干个相同的玩具，某人想将这些玩具重新摆放成为他心中理想的状态，规定移动时只能将玩具向上下左右四个方向移动，并且移动的位置不能有玩具，请你用最少的移动次数将初始的玩具状态移动到目标状态。
代码实现;
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int dx[]={0,0,1,-1}; 4 const int dy[]={1,-1,0,0}; 5 6 char s[10]; 7 int mp[66000],state[5][5],st[5][5],ed[5][5],e; 8 9 int get_hash(int a[5][5]){ 10 int tot=0,p=1; 11 for(int i=1;i<=4;i++) 12 for(int j=1;j<=4;j++) 13 tot+=a[i][j]*p,p<<=1; 14 return tot; 15 } 16 17 void get_state(int x){ 18 for(int i=1;i<=4;i++) 19 for(int j=1;j<=4;j++) 20 state[i][j]=x&1,x>>=1; 21 } 22 23 void read_and_parse(){ 24 for(int i=1;i<=4;i++){ 25 scanf("%s",s+1); 26 for(int j=1;j<=4;j++)st[i][j]=s[j]-'0'; 27 } 28 for(int i=1;i<=4;i++){ 29 scanf("%s",s+1); 30 for(int j=1;j<=4;j++)ed[i][j]=s[j]-'0'; 31 } 32 memset(mp,-1,sizeof(mp)); 33 e=get_hash(ed); 34 } 35 36 void solve(){ 37 queue<int> q; 38 q.push(get_hash(st)),mp[get_hash(st)]=0; 39 while(q.size()){ 40 int u=q.front();q.pop(); 41 if(u==e)break; 42 get_state(u); 43 for(int i=1;i<=4;i++) 44 for(int j=1;j<=4;j++) 45 if(state[i][j]) 46 for(int k=0;k<4;k++){ 47 int x=i+dx[k],y=j+dy[k]; 48 if(x<1||y<1||x>4||y>4)continue; 49 swap(state[i][j],state[x][y]); 50 int v=get_hash(state); 51 if(mp[v]==-1){ 52 q.push(v); 53 mp[v]=mp[u]+1; 54 } 55 swap(state[i][j],state[x][y]); 56 } 57 } 58 printf("%d ",mp[e]); 59 } 60 61 int main(){ 62 read_and_parse(); 63 solve(); 64 return 0; 65 }