2017蓝桥杯C++A组——跳蚱蜢

本文主要是介绍2017蓝桥杯C++A组——跳蚱蜢，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

跳蚱蜢题目链接

问题描述

【题目描述】

【输出】

题目解析

首先设置两个字符串$$start=‘012345678’$$$$target=‘087654321’$$分别表示初始状态和目标状态，利用宽度优先搜索算法，采用队列的数据结构，取出头部状态，接着把相邻的4个状态加入队列，直到到达目标状态为止。

最后输出层数即可。

C++代码

char *start = "012345678";
char *target = "087654321";
struct StateAndLevel
{char *state;int level;int pos0;StateAndLevel(char *_state,int _level,int _pos0):state(_state),level(_level),pos0(_pos0){}
};
struct cmp
{bool operator()(char *a,char *b){return strcmp(a,b);}
};
queue<StateAndLevel> q;
set<char *,cmp> allState;void swap(char *s,int a,int b)
{char t=s[a];s[a] = s[b];s[b] = t;
}void addNei(char *state,int pos,int newPos,int le)
{char * new_state = (char *)malloc(9*sizeof(char));strcpy(new_state,state);swap(new_state,pos,newPos);if(allState.find(new_state)==allState.end()){allState.insert(new_state);q.push(StateAndLevel(new_state,le+1,newPos));}
}int main(int argc,const char *argv[])
{q.push(StateAndLevel(start,0,0));allState.insert(start);while(!q.empty()){StateAndLevel sal = q.front();char *state = sal.state;int le = sal.level;if(strcmp(state,target)==0) //当前状态已经是目标状态{cout<<le<<endl;return 0;}int pos0 = sal.pos0;int new_pos = (pos0-1+9)%9; //添加左一addNei(state,pos0,new_pos,le);new_pos = (pos0-2+9)%9; //添加左二addNei(state,pos0,new_pos,le);new_pos = (pos0+1+9)%9; //添加右一addNei(state,pos0,new_pos,le);new_pos = (pos0+2+9)%9; //添加右二addNei(state,pos0,new_pos,le);q.pop();}return 0;
}

这篇关于2017蓝桥杯C++A组——跳蚱蜢的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---