• admin
• 最少步数德国世界杯成绩

最少步数

时间限制：3000 ms | 内存限制：65535 KB

难度：4

描述

这有一个迷宫，有0~8行和0~8列：

1,1,1,1,1,1,1,1,1 1,0,0,1,0,0,1,0,1 1,0,0,1,1,0,0,0,1 1,0,1,0,1,1,0,1,1 1,0,0,0,0,1,0,0,1 1,1,0,1,0,1,0,0,1 1,1,0,1,0,1,0,0,1 1,1,0,1,0,0,0,0,1 1,1,1,1,1,1,1,1,1

0表示道路，1表示墙。

现在输入一个道路的坐标作为起点，再如输入一个道路的坐标作为终点，问最少走几步才能从起点到达终点？

（注：一步是指从一坐标点走到其上下左右相邻坐标点，如：从（3，1）到（4,1）。）

输入第一行输入一个整数n（0

2

3 1 5 7

3 1 6 7

样例输出

12

11

CODE:

#include#include #include #include #include

using namespace std;

char g[10][10]={"111111111","100100101","100110001","101011011","100001001","110101001","110101001","110100001","111111111"};int dir[4][4]={{-1,0},{0,1},{1,0},{0,-1}};int cnt;int used[9][9];struct node { int x,y,count; }temp,ans;

int main(){ int t,a,b,c,d,i,j,dx,dy; scanf("%d",&t); while(t--) { memset(used,0,sizeof(used));

scanf("%d%d%d%d",&a,&b,&c,&d); queueq//广搜用到队列 temp.x=a; temp.y=b; temp.count=0; q.push(temp); used[a][b]=1; while(!q.empty()) //很重要，深搜循环条件 { ans.x=q.front().x; ans.y=q.front().y; ans.count=q.front().count; q.pop(); if(ans.x==c && ans.y==d) //深搜终止条件，搜到目的点 break; for( i=0;i<4;i++) { if(!used[ans.x+dir[i][0]][ans.y+dir[i][1]]&& (ans.x+dir[i][0])>=0 && (ans.x+dir[i][0])<=8 && (ans.y+dir[i][1])>=0 && (ans.y+dir[i][1])<=8&& g[ans.x+dir[i][0]][ans.y+dir[i][1]]=='0') //找出它的所有邻接点 { used[ans.x+dir[i][0]][ans.y+dir[i][1]]=1; temp.x=ans.x+dir[i][0]; temp.y=ans.y+dir[i][1]; temp.count=ans.count+1; //搜到下一层count加1 q.push(temp); } } } printf("%d\n",ans.count); } return 0;

}