本文主要是介绍P5507 机关，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目背景
Steve成功降落后，在M星上发现了一扇大门，但是这扇大门是锁着的
题目描述
这扇门上有一个机关，上面一共有12个旋钮，每个旋钮有4个状态，将旋钮的状态用数字1到4表示
每个旋钮只能向一个方向旋转（状态：1->2->3->4->1），在旋转时，会引起另一个旋钮也旋转一次（方向相同，不会引起连锁反应），同一旋钮在不同状态下，可能会引起不同的旋钮旋转（在输入中给出）
当所有旋钮都旋转到状态1时，机关就打开了
由于旋钮年久失修，旋转一次很困难，而且时间很紧迫，因此Steve希望用最少的旋转次数打开机关
这个任务就交给你了
输入格式
12行，每行5个整数，描述机关的状态
第i行第一个整数si表示第i个旋钮的初始状态是si
接下来4个整数ai,j=1,2,3,4 表示这个旋钮在状态j时旋转，会引起第ai,j个旋钮旋转到下一个状态
输出格式
第一行一个整数n，表示最少的步数
第二行n个整数，表示依次旋转的旋钮编号
数据保证有解
输入输出样例
输入
3 3 7 2 6 3 1 4 5 3 3 1 2 6 4 3 1 10 3 5 3 2 8 3 6 3 7 9 2 1 1 1 2 3 4 1 3 11 10 12 1 8 6 7 4 1 9 9 8 8 1 12 10 12 12 1 7 8 9 10
输出
6 1 2 3 4 5 6
这道题一看就肯定用搜索来写，先说一下普通搜索的思路，这题第一个想到的肯定是广搜，用广搜找每一步，枚举12个按钮的可能性，中途用一个数组，记录路径，找到终点（全都为1）时，输出步数与路径
下面放一段广搜思路的代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
struct node{int x[13];//现在的状态int path[18]; //保存路径 int step=0;
}n;
int a[13][6];
map<long long,int> vis;
queue<node> q;
int num(int x[]){int res=0;for(int i=1;i<=12;i++)res=res*10+x[i];return res;
}
void bfs(){//起点入队q.push(n);vis[num(n.x)]=1; while(q.size()){node t=n=q.front();q.pop();//可能转动1-12号按钮 for(int i=1;i<=12;i++){//获取转动i号按钮后的状态n.x[ a[i][n.x[i]]]++;if(n.x[ a[i][n.x[i] ] ]==5)n.x[ a[i][n.x[i] ] ]=1;n.x[i]++;if(n.x[i]==5)n.x[i]=1;int b=num(n.x);if(vis[b]==1){n=t;continue;}vis[b]=1;n.path[n.step++]=i;if(b==111111111111){//终点判断printf("%lld\n",n.step);for(int j=0;j<n.step;j++)printf("%lld ",n.path[j]);return;}q.push(n);n=t;}}
}
signed main(){for(int i=1;i<=12;i++)for(int j=0;j<5;j++)scanf("%lld",&a[i][j]);for(int i=1;i<=12;i++)n.x[i]=a[i][0];bfs();
}交上去我们就会发现只AC了四个，其他全都TLE了。
那么这个时候，我们就要对代码进行优化。
双向广搜我不太推荐，因为要输出路径，双向广搜输出比较麻烦，所以这里呢就改成A*吧
A*算法就是在所有的节点中选择最优的（最容易到达终点的），这样可以节省许多时间，就好比找东西，先去找可能性更大的，没找到再去找可能性更小的，因此需要一个估价函数，来预估现在的价值，价值更小的也就是我们的优先搜索对象了。
这里我们的价值，就是到终点距离（这道题就是步数）加上已走的步数，估价函数所估计的，就是还要的步数。
好，回归正题，所以就要用优先队列来存储值，给优先队列写一个排序规则，按照val（价值）升序排列，每次照样取队头就行了。
但是，这个估价函数不能偷懒，如果你只返回有几个不一样的值，就会发现，还有一个TLE死犟死犟的，一直A不了
这里的估价函数，得写成每个点距离1还要几步。
完整代码如下：
#include<bits/stdc++.h>
#define int long long
using namespace std;
int h(int x[]){//求出预估值int cnt=0;for(int i=1;i<=12;i++){int ans=x[i];int s=0;while(ans!=1){ans++;s++;if(ans==5){ans=1;}}cnt+=s;}return cnt;
}
struct node{int x[13];//用来存当前状态int path[18]; //保存路径 int step=0;//记录步数int val=0;//存预估值friend bool operator <(node a,node b){//优先队列的排序规则return a.val>b.val;}
}n;
int a[13][6];//用于输入和带动
map<int,int>vis;//vis用来标记
priority_queue<node> q;//创建优先队列
int num(int x[]){int res=0;for(int i=1;i<=12;i++)res=res*10+x[i];//数组转化为数字return res;
}
void bfs(){//起点入队n.val=h(n.x)+0;//求起点的预估值q.push(n);//起点入队vis[num(n.x)]=1;//记录while(!q.empty()){node t=n=q.top();//获取队头q.pop();//队头出队//可能转动1-12号按钮 for(int i=1;i<=12;i++){//循环，遍历每一个按钮//获取转动i号按钮后的状态n.x[ a[i][n.x[i]]]++;//被联动的按钮做改变if(n.x[ a[i][n.x[i] ] ]==5)n.x[ a[i][n.x[i]] ]=1;//边界判断n.x[i]++;//当前按钮做改变if(n.x[i]==5)n.x[i]=1;//判断边界int b=num(n.x);//转化为数字if(vis[b]==1){//如果这个状态找过，直接跳过n=t;//返回原来状态continue;//跳过这次循环}vis[b]=1;//标记当前状态n.val=h(n.x)+n.step;//记录当前预估值n.path[n.step++]=i;//路径记录数组记录路径if(b==111111111111){//如果到达了终点，输出printf("%lld\n",n.step);//输出次数for(int j=0;j<n.step;j++)printf("%lld ",n.path[j]);//输出方法return;}q.push(n);//将当前状态入队n=t;//回到原来的值}}
}
signed main(){//输入for(int i=1;i<=12;i++)for(int j=0;j<5;j++)scanf("%lld",&a[i][j]);//初始化起点状态:333333111111 for(int i=1;i<=12;i++)n.x[i]=a[i][0];//取每个按钮的当前状态bfs();//调用函数
}这篇关于P5507 机关的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
