最短路问题------分别用深搜和广搜去解题

最少步数
时间限制：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<n<=100），表示有n组测试数据;
随后n行,每行有四个整数a,b,c,d（0<=a,b,c,d<=8）分别表示起点的行、列，终点的行、列。
输出
输出最少走几步。
样例输入
2
3 1  5 7
3 1  6 7
样例输出
12
11

下面附上深搜的代码

广度优先搜索特点是从一个点开始以圆形的方式向周围开始扩散广搜常用于找单一的最短路线，或者是规模小的路径搜索，它的特点是"搜到就是最优解广搜则是操作了队列，先被扩年夜的的节点优先拿往扩年夜。

 1 //   广搜  每个点走一边 就得到了   从原点 到  终点的 最短距离
 2 #include<iostream>
 3 #include<queue>
 4 #include<stdio.h>
 5 #include<string.h>
 6 #include<cstring>
 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,1
19 };
20 struct node
21 {
22     int x,y,step;  //节点的坐标和 距离起点 路程
23 };
24 queue<node> 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
",k);
68     }
69     return 0;
70 }

 1 #include <stdio.h>
 2 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,1
14 };
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
",ans);
44     }
45     return 0;
46 }