ABC007-C 幅優先探索（AtCoder精進記録）

C - 幅優先探索

AtCoder Beginner Contest 007-C

〇問題
・'x# : 壁、'.' : 道
例：

########
#......#
#.######
#..#...#
#..##..#
##.....#
########

スタートとゴールが与えられ、その最短経路の歩数を求める。

〇方針
・幅優先探索

〇ソースコード（C言語）

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <stdbool.h>

int row,column;
char c[51][51]; 
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
bool reached[50][50];
int qx[3000],qy[3000];
int step[51][51];
int head=0,tail=1;

// 幅優先探索
void bfs(int x,int y);

int main()
{
    int row_start,column_start;
    int row_goal,column_goal;
    scanf("%d%d",&row,&column);
    scanf("%d%d",&row_start,&column_start);
    scanf("%d%d",&row_goal,&column_goal);
    for(int i=0;i<row;i++){
        scanf("%s",c[i]);
    }

    bfs(row_start-1,column_start-1);
    printf("%d\n",step[row_goal-1][column_goal-1]);

    return 0;
}

void bfs(int x,int y){
    reached[x][y] = true;
    qx[0] = x;
    qy[0] = y;
    step[x][y] = 0;
    while( head != tail ){
        // Pop(取り出し)
        int poped_x = qx[head];
        int poped_y = qy[head];
        head++;
        for(int i=0;i<4;i++){
            int nx = poped_x + dx[i];
            int ny = poped_y + dy[i];
            // 迷路の範囲内であるか
            if( ( nx >= 0 ) && ( nx < row ) && ( ny >= 0 ) && ( ny < column ) ){
                // まだ未到達かつ道であるか
                if( (reached[nx][ny] == false) && ( c[nx][ny] == '.' ) ){
                    step[nx][ny] = step[poped_x][poped_y] + 1;
                    reached[nx][ny] = true;
                    // Push(追加)
                    qx[tail] = nx;
                    qy[tail] = ny;
                    tail++;
                }
            }
        }
    }
}

〇所感
・聞いたことはあるけど実装したことがないやつ。あいまいな理解だったところがようやくすっきりした。
・もうちょい練習は必要かな…
・深さ優先探索もそうだけど、これを知らずによくC問題まで安定して解いてんな…と思った。今までは運がよかっただけかも。

〇参考記事
・AtCoder 版！蟻本 (初級編)　（問題の選択）

〇参考コード
・Submission #1960299 - AtCoder Beginner Contest 007
　チラ見して、考えて、チラ見して…って感じに使わせていただいた。