NO3——BFS

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <queue>
 4 using namespace std;
 5 
 6 struct node
 7 {
 8     int x,y,step;
 9 };
10 
11 char map[105][105];
12 int vis[105][105];
13 int to[4][2]= {1,0,-1,0,0,1,0,-1};
14 int n,m,sx,sy,ex,ey,ans;
15 
16 int check(int x,int y)
17 {
18     if(x<0 || x>=n || y<0 || y>=m)
19         return 1;
20     if(vis[x][y] || map[x][y]=='#')
21         return 1;
22     return 0;
23 }
24 
25 void bfs()
26 {
27     int i;
28     queue<node> Q;
29     node a,next;
30     a.x = sx;
31     a.y = sy;
32     a.step = 0;
33     vis[a.x][a.y]=1;
34     Q.push(a);
35     while(!Q.empty())
36     {
37         a = Q.front();
38         Q.pop();
39         if(map[a.x][a.y]=='E')
40         {
41             ans = a.step;
42             return ;
43         }
44         for(i = 0; i<4; i++)
45         {
46             next = a;
47             next.x+=to[i][0];
48             next.y+=to[i][1];
49             if(check(next.x,next.y))
50                 continue;
51             next.step=a.step+1;
52             vis[next.x][next.y] = 1;
53             Q.push(next);
54         }
55     }
56     ans = -1;
57 }
58 
59 int main()
60 {
61     int t;
62     scanf("%d",&t);
63     while(t--)
64     {
65         scanf("%d%d",&n,&m);
66         int i,j;
67         for(i = 0; i<n; i++)
68             scanf("%s",map[i]);
69         for(i = 0; i<n; i++)
70         {
71             for(j = 0; j<m; j++)
72             {
73                 if(map[i][j]=='S')
74                 {
75                     sx = i;
76                     sy = j;
77                 }
78             }
79         }
80         memset(vis,0,sizeof(vis));
81         bfs();
82         printf("%d
",ans);
83     }
84 
85     return 0;
86 }