【算法实验三】(BFS |
您所在的位置:网站首页 › 在九宫格里画画 › 【算法实验三】(BFS |
1571.八数码
时限:5000ms 内存限制:20000K 总时限:10000ms 描述 在九宫格里放在1到8共8个数字还有一个是空格,与空格相邻的数字可以移动到空格的位置,问给定的状态最少需要几步能到达目标状态(用0表示空格): 1 2 3 4 5 6 7 8 0
输入 输入一个给定的状态。
输出 输出到达目标状态的最小步数。不能到达时输出-1。
输入样例 1 2 3 4 0 6 7 5 8
输出样例 2 #include #include #include #include using namespace std; /********************/ struct state { int a[3][3]; int zx,zy; int integer;//map->9位数 int useful;//若0位置越界或节点重复,则为无效节点 }; state start; queue q; map used; map step; int walk[4][2]= { 0,-1,//left +1,0,//down 0,+1,//right -1,0//up }; /*******************/ int bfs(); int setinteger(state n); state move(state now,int i); /******************/ void init() { for(int i=0;istart.a[i][j]; if(start.a[i][j]==0) { start.zx=i; start.zy=j; } } start.integer=setinteger(start); used[start.integer]=1; step[start.integer]=0; q.push(start); } int setinteger(state n) { n.integer=0; for(int i=0;i |
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |
CopyRight 2018-2019 实验室设备网 版权所有 win10的实时保护怎么永久关闭 |