BFS 幅優先探索

幅優先探索を使ってスタートからゴールまでの道のりを計算するらしい。

#include<stdio.h>
#include<queue>
typedef std::pair<int ,int> P;
int bfs();
const int INF = 500;

char maze[10][11] = {"#S######.#","......#..#",".#.##.##.#",".#........","##.##.####","....#....#",".#######.#","....#.....",

".####.###.","....#...G#"};

int N = 10,M = 10;
int sx = 1,sy = 0;
int gx = 8,gy = 9;

int d[10][10];

int dy[4] = {1,0,-1,0} , dx[4] = { 0,1,0,-1,};

int bfs(){
    int i,j;
    int nx,ny;

    std::queue<P> que;
    for(i = 0;i < 10;i++){
        for(j = 0;j < 10;j++){
            d[i][j] = INF;
        }
    }
    que.push(P(sy,sx));
    d[sy][sx] = 0;
   
    while(que.size()){
        P p = que.front();
        que.pop();
        if(p.first == gy && p.second == gx){
            break;
        }
        for(i = 0;i < 4;i++){
            ny = p.first + dy[i];
            nx = p.second + dx[i];
           
            if(0 <= ny && ny < N && 0 <= nx && nx < M && maze[ny][nx] != '#' && d[ny][nx] == INF){
                que.push(P(ny,nx));
                d[ny][nx] = d[p.first][p.second] + 1;
            }
        }
    }
    return d[gy][gx];
}

int main(void){
    int ans;
    ans = bfs();
    printf("%d\n",ans);
    for(int i = 0; i < 10; i++){
        printf("%s\n",maze[i]);
    }
    return 0;
}