本文共 2570 字，大约阅读时间需要 8 分钟。
题目大意：
有一张图，上面的路径都是着色的，开始的时候有3个盘子在确定的点上，现在让你按要求沿图中的路径移动盘子（一步只能移动一只盘子），问是否能将3个盘子都移到同一个点上，如果可以，输出需要的最少步数，否则输出“impossible”。移动条件是：每个盘子只能沿着这样一条路移动，这条路的颜色和另外的两个盘子之间的路径上标记的颜色是一样的。解题思路：
BFS入门题，比较直接的BFS题目,图为无向完全图,也就是n个点有n(n-1)/2条边，每两个点都有一条直通边，就是中间没有其他点，也可以理解为本身就是自己的最大团，这个条件也让题目更加方便简单；首先把三个盘子的每个点的位置想象成一个三维坐标（x,y,z），这样题目中说的三个盘子移动到一起，不就是判断移动到的位置是否满足（x==y&&y==z）这个关系吗？所以题目就简单化了，只要分别向x,y,z三个方向搜索（因为每次只能移动一步），每次搜索只需要判断盘子此时点的位置是否可以移动到邻接点位置（就是这条路的颜色和另外的两个盘子之间的路径上标记的颜色是否是一样的），可以的话就更新位置和该位置点的步数，再判断是否满足（x==y&&y==z）这个条件即可，不满足再执行上面的操作，最多循环到queue.empty()为true，就会出结果。 AC代码:
#include#include #include #include #include #include #include #include #include #include #include using namespace std;const int INF=0x3f3f3f3f; //一般认为无穷大 #define MEM(a,x) memset(a,x,sizeof(a)) #define F(i,n) for(i=1;i<=n;i++)int cnt[55][55][55]; //记录每个位置的最小步数 char map[55][55]; //存图 bool isok; //存储是否可以移动到一起的结果 int n,p1,p2,p3; struct Point{ int x,y,z; Point(int x_=0,int y_=0,int z_=0):x(x_),y(y_),z(z_){ }}; /*BFS中queue的成员，用来存储位置 ，结构体中的构造函数方便直接将位置push到queue中 */typedef Point P; //Point结构体变量以后可以直接用P定义，方便一点 int BFS(){ fill(&cnt[0][0][0],&cnt[0][0][0]+55*55*55,INF);//cnt数组初始赋值无穷大 cnt[p1][p2][p3]=0;//初始点为0步 queue
que; P p; int x,y,z; int i; int cnt_type; //记录步数，方便下一步操作 string color; //记录一个点的所以的边的颜色 char color_mid; //记录另外两个之间的颜色 que.push(P(p1,p2,p3)); //初始位置入队 isok=false; //还没有移动到一起，为false while(!que.empty()) { p=que.front(); que.pop(); x=p.x; y=p.y; z=p.z; if(x==y&&y==z) { isok=true; //移动到一起，为true return x; //返回下标，方便在main方法中输出步数 } else{ cnt_type=cnt[x][y][z]; //当前位置步数 cnt_type++; //更新位置步数=当前位置步数+1 //分别 向x,y,z移动 color_mid=map[y][z]; //点yz之间的颜色 color=map[x]; //点x所以边的颜色 F(i,n) { if(color[i]==color_mid&&i!=x&&cnt[i][y][z]>cnt_type) /*点x移动的边颜色和点yz之间的颜色相同 ，并且不同点，并且小于其原来的步数*/ { cnt[i][y][z]=cnt_type; //赋值更新位置的步数 que.push(P(i,y,z)); //加入更新的位置 } } //下面一样 color_mid=map[x][z]; color=map[y]; F(i,n) { if(color[i]==color_mid&&i!=y&&cnt[x][i][z]>cnt_type) { cnt[x][i][z]=cnt_type; que.push(P(x,i,z)); } } color_mid=map[x][y]; color=map[z]; F(i,n) { if(color[i]==color_mid&&i!=z&&cnt[x][y][i]>cnt_type) { cnt[x][y][i]=cnt_type; que.push(P(x,y,i)); } } } } return -1;}int main(){ while(cin>>n&&n) { int i,j; cin>>p1>>p2>>p3; F(i,n) { map[i][0]=' '; /*需要加上，经验吧，不加，可能错，因为不同的编译器， 可能有不同的默认值 ，有可能没有值，所以赋给string变量可能会出错 */ F(j,n) { cin>>map[i][j]; /*比较少的输入输出用 c++的io个人感觉比较好， 虽然对时间效率不友好，但是对输入输出方式很友好，因为输出中有空格*/ } map[i][n+1]='\0'; //结束字符，因为要赋给string变量 } //存图 int end=BFS(); if(isok) printf("%d\n",cnt[end][end][end]); else { printf("impossible\n"); } } return 0;}
转载地址：https://kaven.blog.csdn.net/article/details/76593669 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！
发表评论
最新留言
关于作者
