首页 > 代码库 > 【判重+广搜（bfs）】魔板
【判重+广搜（bfs）】魔板
判重+广搜（bfs）】魔板
Time Limit: 1000MS
Memory Limit: 32768KB
Special Judge
有一个两行四列的魔板，每个格子里有一个1到8的数字（数字唯一），现在我们可以对魔板进行以下操作：
1.交换两行的数字。
2.将第一列移到第二列，第二列到第三列，第三列到第四列，第四列到第一列。
3.将中间四个数顺时针转一次。
现给你初始状态，我末状态请你用最小的步数将它从初始状态变到末状态。
输入：
前两行，每行4个数表示初状态。
后两行，每行4个数表示末状态。
输出：
第一行一个数，表示最少步数。
接下来每两行一个状态，依次给出从初状态到末状态的过程。
样例：
输入：
1 2 3 4
5 6 7 8
2 3 4 1
6 7 8 5
输出：
3
1 2 3 4
5 6 7 8
4 1 2 3
8 5 6 7
3 4 1 2
7 8 5 6
2 3 4 1
6 7 8 5
Source
class
judge
1 # include<cstdio> 2 # include<cstring> 3 # include<algorithm> 4 # include<iostream> 5 using namespace std; 6 const int maxn=40000; 7 int map[maxn][3][5],pre[maxn],end[3][5],num[maxn],vis[maxn]; 8 int head=1,tail=1,cur; 9 void init(){10 for(int i=1;i<=2;i++)for(int j=1;j<=4;j++)scanf("%d",&map[1][i][j]);11 for(int i=1;i<=2;i++)for(int j=1;j<=4;j++)scanf("%d",&end[i][j]);12 }13 int check(int head){14 for(int i=1;i<=2;i++)15 for(int j=1;j<=4;j++)16 if(map[head][i][j]!=end[i][j])17 return 0;18 return 1;19 }20 void one(){21 tail++;22 for(int i=1;i<=4;i++)map[tail][1][i]=map[head][2][i];23 for(int i=1;i<=4;i++)map[tail][2][i]=map[head][1][i];24 pre[tail]=head;25 num[tail]=num[head]+1;26 }27 void two(){28 tail++;29 map[tail][1][1]=map[head][1][4];30 map[tail][2][1]=map[head][2][4];31 map[tail][1][2]=map[head][1][1];32 map[tail][2][2]=map[head][2][1];33 map[tail][1][3]=map[head][1][2];34 map[tail][2][3]=map[head][2][2];35 map[tail][1][4]=map[head][1][3];36 map[tail][2][4]=map[head][2][3];37 pre[tail]=head;38 num[tail]=num[head]+1;39 }40 void tree(){41 tail++;42 for(int i=1;i<=2;i++)for(int j=1;j<=4;j++)43 map[tail][i][j]=map[head][i][j];44 map[tail][1][2]=map[head][2][2];45 map[tail][1][3]=map[head][1][2];46 map[tail][2][3]=map[head][1][3];47 map[tail][2][2]=map[head][2][3];48 pre[tail]=head;49 num[tail]=num[head]+1;50 }51 void print(int head){52 printf("%d\n",num[head]);53 for(int i=pre[head];i!=0;i=pre[i])54 vis[++cur]=i;55 for(int i=cur;i>=1;i--)56 for(int j=1;j<=2;j++){57 for(int k=1;k<=4;k++)58 printf("%d ",map[vis[i]][j][k]);59 printf("\n");60 }61 for(int j=1;j<=2;j++){62 for(int k=1;k<=4;k++)63 printf("%d ",end[j][k]);64 printf("\n");65 }66 }67 void bfs(){68 while(head<=tail){69 if(check(head)){70 print(head);71 return;72 }73 one();74 two();75 tree();76 head++;77 }78 }79 int main(){80 init();81 bfs();82 return 0;83 }
【判重+广搜（bfs）】魔板
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。