【跳蚱蜢】2017年第八届蓝桥杯【C/C++省赛A组】

绝地灬酷狼 2023-02-28 11:16 19阅读 0赞

题目：跳蚱蜢  
如下图所示：  
![在这里插入图片描述][20200512201718241.png]  
  有9只盘子，排成1个圆圈。其中8只盘子内装着8只蚱蜢，有一个是空盘。  
  我们把这些蚱蜢顺时针编号为 1~8，每只蚱蜢都可以跳到相邻的空盘中，  
  也可以再用点力，越过一个相邻的蚱蜢跳到空盘中。**请你计算一下，如果要使得蚱蜢们的队形改为按照逆时针排列，并且保持空盘的位置不变（也就是1-8换位，2-7换位,…），至少要经过多少次跳跃？**  
  注意：要求提交的是一个整数，请不要填写任何多余内容或说明文字。

思路分析：从一个状态到另一个状态最少需要多少步骤，毫无疑问就是BFS问题。此题与人工智能中的经典问题–八数码问题差不多类似。先将字符串012345678入队列，然后出队列，按照规则产生新的字符串，如果该字符串就是目标字符串那么就终止，如果不是且以前没有出现过，那么就入队列，重复上述操作即可。  
  从分析来看，我们需要解决以下几个问题：

1.  怎么判重？这个其实很简单，C++判重一般就考虑set就可以了，将每一种新产生字符串放入set就可以达到目标。
2.  怎么产生新的字符串？  
    ![在这里插入图片描述][20200512201718241.png]  
    我们再仔细观察这张图：我们将空盘记为0,第一轮开始，1和8都可以跳到0位置，另外7和2也可以跳到空盘里。因此每一轮都可以产生四个新的状态。我们可以定义一个数组包含1,2，-1，-2四个数来表示四个方位，用当前位置+9再对9取模即是**要跟空盘交换的位置**。
3.  怎么记录这些状态？空盘位置在变，而我们每一次跳跃都是以空盘为基础的，所以空盘的位置在每个状态必须被记录下来；另外字符串长啥样也要记录下来，此外还有跳跃的次数也要记录下来。因此我们可以定义一个结构体，里面包含pos和s以及cnt三个变量。  
    代码：

#include<bits/stdc++.h>
    using namespace std;
    
    struct state { 
    	int pos,cnt;    //pos记录当前空盘位置，cnt记数，表示走了几步 
    	char *s;        //当前字符串 
    	state(int pos,char *s,int cnt):pos(pos),s(s),cnt(cnt){ }  //构造函数 
    };
    struct cmp { 
    	bool operator()(char *a,char *b) { 
    		return strcmp(a,b)>0;
    	}
    };
    
    int change[4]={ -1,-2,1,2},cnt=1;   //change表示四个位置，左1左2，右1右2 
    char *start="012345678",*end="087654321";
    queue<state> q;
    set<char *,cmp> check;
    
    void swap(char *s,int a,int b) { 
    	char t=s[a];
    	s[a]=s[b];
    	s[b]=t;
    }
    
    int bfs() { 
    	q.push(state(0,start,0));   //初始状态入队 
    	while(!q.empty()) { 
    		state temp=q.front();  //获取当前队头结点 
    		int pos=temp.pos;
    		int cnt=temp.cnt;
    		char *s=temp.s;
    		check.insert(s);
    		if(strcmp(s,end)==0) {    //已经找到就结束 
    			cout<<cnt;
    			return 0;
    		}
    		q.pop();
    		//产生新字符串入队 
    		for(int i=0;i<4;i++) { 
    			char *t=(char*)malloc(9*sizeof(char));
    			strcpy(t,s);
    			int newpos=(pos+change[i]+9)%9;   //交换后新的空盘位置 
    			swap(t,pos,newpos);               //交换 
    			if(check.find(t)==check.end()) {    
    				check.insert(t);
    				q.push(state(newpos,t,cnt+1));  //新结点入队 
    			}
    		}
    	}
    }
    
    int main() { 
    	bfs();
    	return 0;
    }

答案：20

[20200512201718241.png]: /images/20230209/e236f9ac3d3f400da4a6d2efcfaea1ff.png