最少步数时间限制：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,10表示道路，1表示墙。现在输入一个道路的坐标作为起点，再如输入一个道路的坐标作为终点，问最少走几步才能从起点到达终点？（注：一步是指从一坐标点走到其上下左右相邻坐标点，如：从（3，1）到（4,1）。）输入第一行输入一个整数n（0<=100），表示有n组测试数据;随后n行,每行有四个整数a,b,c,d（0<=a,b,c,d<=8）分别表示起点的行、列，终点的行、列。输出输出最少走几步。样例输入23 1 5 73 1 6 7样例输出1211
下面附上 深搜的代码
广度优先搜索特点是从一个点开始以圆形的方式 向周围 开始扩散广搜常用于找单一的最短路线，或者是规模小的路径搜索，它的特点是"搜到就是最优解广搜则是操作了队列，先被扩年夜的的节点优先拿往扩年夜。
1 // 广搜 每个点走一边 就得到了 从原点 到 终点的 最短距离 2 #include3 #include 4 #include 5 #include 6 #include 7 using namespace std; 8 int a[9][9]= 9 {10 1,1,1,1,1,1,1,1,1,11 1,0,0,1,0,0,1,0,1,12 1,0,0,1,1,0,0,0,1,13 1,0,1,0,1,1,0,1,1,14 1,0,0,0,0,1,0,0,1,15 1,1,0,1,0,1,0,0,1,16 1,1,0,1,0,1,0,0,1,17 1,1,0,1,0,0,0,0,1,18 1,1,1,1,1,1,1,1,119 };20 struct node21 {22 int x,y,step; //节点的坐标和 距离起点 路程23 };24 queue Q;25 int c[4]={ 0,0,-1,1},b[4]={-1,1,0,0},visite[9][9];26 int bfs(int x1,int y1,int x2,int y2)27 {28 int i,s,t;29 node e={x1,y1,0}; // 从这一点开始走30 visite[x1][y1]=1;31 Q.push(e); // 原点 压进去32 while(!Q.empty())33 {34 e=Q.front(); // 队首 元素 取出来35 if(e.x==x2&&e.y==y2)36 {37 break; //跳出去的时候 节点e 就是 终点38 }39 Q.pop();40 for(i=0;i<4;i++)41 {42 s=e.x+c[i];43 t=e.y+b[i];44 if(s<=8&&s>=0&&t>=0&&t<=8&&!visite[s][t]&&!a[s][t])45 {46 node e1={s,t,e.step+1};47 Q.push(e1);48 visite[s][t]=1;49 }50 }51 }52 if(Q.empty())53 return -1;54 while(!Q.empty())55 Q.pop();56 return e.step;57 }58 int main()59 {60 int k,n,x1,x2,y1,y2;61 scanf("%d",&n);62 while(n--)63 {64 memset(visite,0,sizeof(visite));65 scanf("%d%d%d%d",&x1,&y1,&x2,&y2);66 k=bfs(x1,y1,x2,y2);67 printf("%d\n",k);68 }69 return 0;70 }
1 #include2 int ans,sx,sy,ex,ey; 3 bool vis[9][9],map[9][9]= 4 { 5 1,1,1,1,1,1,1,1,1, 6 1,0,0,1,0,0,1,0,1, 7 1,0,0,1,1,0,0,0,1, 8 1,0,1,0,1,1,0,1,1, 9 1,0,0,0,0,1,0,0,1,10 1,1,0,1,0,1,0,0,1,11 1,1,0,1,0,1,0,0,1,12 1,1,0,1,0,0,0,0,1,13 1,1,1,1,1,1,1,1,114 };15 16 void dfs(int i,int j,int cnt)17 {18 if(i<0||i>8||j<0||j>8||vis[i][j]||map[i][j]||cnt>=ans)19 return;20 if(i==ex&&j==ey)21 {22 ans=cnt;23 return;24 }25 vis[i][j]=1; // 这个已经遍历了x`26 dfs(i,j-1,cnt+1);27 dfs(i-1,j,cnt+1);28 dfs(i,j+1,cnt+1);29 dfs(i+1,j,cnt+1);30 31 vis[i][j]=0;32 }33 34 int main()35 {36 int n;37 scanf("%d",&n);38 while(n--)39 {40 scanf("%d%d%d%d",&sx,&sy,&ex,&ey);41 ans=100;42 dfs(sx,sy,0);43 printf("%d\n",ans);44 }45 return 0;46 }