BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <bits/stdc++.h>

using namespace std;

const int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};

char mmap[105][105];

struct node{
int x,y;
int step;
};

int bfs(int x,int y,int h,int w){
    vector<vector<bool>> visited(h+1,vector<bool>(w+1,false));
    queue<node> q;
    node start;
    start.x = x;
    start.y = y;
    start.step = 0;
    q.push(start);
    visited[x][y]=true;

    int ans=-1;
    while(!q.empty()){
        node cur=q.front();
        q.pop();

        if(mmap[cur.x][cur.y]=='E'){
            ans=cur.step;
            break;
        }

        for(int i=0;i<4;i++){
            int nx=cur.x+dir[i][0];
            int ny=cur.y+dir[i][1];

            if(nx>=1&&nx<=h&&ny>=1&&ny<=w&&!visited[nx][ny]&&(mmap[nx][ny]=='*'||mmap[nx][ny]=='E')){
                node next;
                next.x = nx;
                next.y = ny;
                next.step = cur.step + 1;
                q.push(next);
                visited[nx][ny]=true;
            }
        }
    }
    return ans;
}

int main ()
{
    int h,w;
    while(cin>>h>>w){
        if(h==0&&w==0) break;
        int sx = 0, sy = 0; // 初始化，避免未赋值警告
        for(int i=1;i<=h;i++){
            string line;
            cin>>line;
            for(int j=1;j<=w;j++){
                mmap[i][j]=line[j-1];
                if(mmap[i][j]=='S'){
                    sx=i;
                    sy=j;
                }
            }
        }
        int ans=bfs(sx,sy,h,w);
        cout<<ans<<endl;
    }
}

诺丁塔

img