广度优先搜索,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
#include <iostream>
#include <queue>
#define INF 99999999
using namespace std;
typedef pair<int,int> P;
char a[20][20];
int step[500][500];  //步数
int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};

int sx=0,sy=0;
int gx=2,gy=3;
int bfs(){
    queue<P> que;
    for(int i=0;i<5;i++)
        for(int j=0;j<5;j++)
            step[i][j]=INF;
    que.push(P(sx,sy));
    step[sx][sy]=0;
    while(que.size()){
        P p=que.front();que.pop();
        if(p.first==gx&&p.second==gy)
            break;
        for(int i=0;i<4;i++){
            int nx=p.first+dir[i][0];
            int ny=p.second+dir[i][1];
            if(nx>=0&&nx<5&&ny>=0&&ny<5&&a[nx][ny]!='#'&&step[nx][ny]==INF){
                que.push(P(nx,ny));
                step[nx][ny]=step[p.first][p.second]+1;
            }
        }
    }
    return step[gx][gy];
}
int main(){
    for(int i=0;i<5;i++)
        for(int j=0;j<5;j++)
            cin>>a[i][j];
    int res=bfs();
    cout<<res;
    return 0;
}