백준 2178 미로찾기

BFS를 이용하는 문제

최단 거리를 구하라고 하길래 A* 알고리즘을 쓰라는 말인가?

싶었는데 그냥 BFS만 사용하면 되는 문제였다

#include<cstdio>
#include<iostream>
#include<queue>
#include <string>
using namespace std;

string arrstr[100];
int X,Y;
int map[101][101];
int mapScore[101][101] = { 0 };
int flag[101][101] = { 0 };
int dx[4] = { 0, 1, 0, -1 };
int dy[4] = { -1, 0, 1, 0 };
bool inside(int x, int y) {
    if (0 <= x && x < X && 0 <= y && y < Y)
        return true;
    else
        false;
}
void BFS(int x, int y) {
    flag[x][y] = true;
    queue<pair<int, int>> q;
    q.push(make_pair(x, y));
    while (!q.empty()) {
        int qX = q.front().first;
        int qY = q.front().second;

        if (qX == X - 1 && qY == Y - 1) {
            cout << mapScore[qX][qY] + 1;
            return;
        }
        q.pop();
        for (int i = 0; i < 4; i++) {
            int CheckX = qX + dx[i];
            int CheckY = qY + dy[i];
            if (map[CheckX][CheckY] == 1 && flag[CheckX][CheckY] == false && inside(CheckX, CheckY)) {
                mapScore[CheckX][CheckY] = mapScore[qX][qY] + 1;
                flag[CheckX][CheckY] = true;
                q.push(make_pair(CheckX, CheckY));
            }
        }
    }
}
int main(void) {
    int i;

    cin >> X >> Y;
    for (i = 0; i < X; i++) {
        cin >> arrstr[i];
    }
    for (int x = 0; x < X; x++) {
        for (int y = 0; y < Y; y++) {
            map[x][y] = arrstr[x][y] - 48;
        }
    }
    BFS(0, 0);
    return 0;
}