2014 网选 5012 Dice(bfs模板)

 /*
题意:就是给定两个筛子,每个筛子上6个面,每个面的数字属于[1,6], 且互不相同!
问a筛子最少经过按照题目规定的要求转动,达到和b筛子上下左右前后的数字相同! 思路:很直白的bfs,将每一种状态对应一个数字,保证这种状态不会重新加入队列中!
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std; int a[], ss;
int vis[]; struct node{
int k[];
node(){}
node(int a1, int a2, int a3, int a4, int a5, int a6){
k[]=a1;
k[]=a2;
k[]=a3;
k[]=a4;
k[]=a5;
k[]=a6;
}
int step;
}; queue<node>q; int sum(node x){
int s=;
for(int i=; i<=; ++i)
s= s* + x.k[i];
return s;
} bool bfs(){
while(!q.empty()) q.pop();
node cur(a[], a[], a[], a[], a[], a[]);
cur.step=;
q.push(cur);
vis[sum(cur)]=;
while(!q.empty()){
cur = q.front();
if(sum(cur)==ss){
printf("%d\n", cur.step);
return true;
}
q.pop();
node *nt = new node(cur.k[], cur.k[], cur.k[], cur.k[], cur.k[], cur.k[]);
int v = sum(*nt);
if(!vis[v]){
vis[v]=;
nt->step = cur.step + ;
q.push(*nt);
} nt = new node(cur.k[], cur.k[], cur.k[], cur.k[], cur.k[], cur.k[]);
v = sum(*nt);
if(!vis[v]){
vis[v]=;
nt->step = cur.step + ;
q.push(*nt);
} nt = new node(cur.k[], cur.k[], cur.k[], cur.k[], cur.k[], cur.k[]);
v = sum(*nt);
if(!vis[v]){
vis[v]=;
nt->step = cur.step + ;
q.push(*nt);
} nt = new node(cur.k[], cur.k[], cur.k[], cur.k[], cur.k[], cur.k[]);
v = sum(*nt);
if(!vis[v]){
vis[v]=;
nt->step = cur.step + ;
q.push(*nt);
}
}
return false;
} int main(){
while(scanf("%d%d%d%d%d%d", &a[], &a[], &a[], &a[], &a[], &a[])!=EOF){
ss=;
for(int i=; i<=; ++i){
int x;
scanf("%d", &x);
ss = ss * + x;
}
memset(vis, , sizeof(vis));
if(!bfs())
printf("-1\n");
}
return ;
}
上一篇:oracle数据库自学笔记(持续更新中……)


下一篇:更新日志 - BugHD 新增邮件告警功能