[ACWing] 844. 미로 로

제목 주소:
https://www.acwing.com/problem/content/846/
주어진 m× n m\times n m×n 2 차원 0 - 1 0 - 1 - 1 매트릭스, 000 은 공 터 를 대표 하고 11 은 장애물 을 대표 한다.(1, 1) (1, 1) (1, 1) 에서 출발 하여 매번 상하 좌우 로 한 걸음 씩 걸 을 수 있 고 장애물 에 올 라 갈 수 없다.(m, n) (m, n) (m, n) 까지 가 려 면 적어도 몇 걸음 은 가 야 하 는 지 물 어 봐 야 한다.
데이터 범위: 1 ≤ n, m ≤ 1000 1 \ \ le n, m \ le 1000 1 ≤ n, m ≤ 1000
BFS 로 하면 됩 니 다.코드 는 다음 과 같 습 니 다:

#include 
#include 

using namespace std;

typedef pair<int, int> PII;

const int N = 110;
int a[N][N];
bool visited[N][N];

int main() {
     
    int m, n;
    cin >> m >> n;

    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            cin >> a[i][j];

    if (m == 1 && n == 1) {
     
        cout << 0 << endl;
        return 0;
    }

    int res = 0;
    queue<PII> q;
    q.push(make_pair(1, 1));
    int d[] = {
     1, 0, -1, 0, 1};
    while (!q.empty()) {
     
        res++;
        int s = q.size();
        for (int i = 0; i < s; i++) {
     
            PII pair = q.front();
            q.pop();
            for (int j = 0; j < 4; j++) {
     
                int nextX = pair.first + d[j], nextY = pair.second + d[j + 1];
                if (nextX == m && nextY == n) {
     
                    cout << res << endl;
                    return 0;
                }

                if (1 <= nextX && nextX <= m && 1 <= nextY && nextY <= n && a[nextX][nextY] == 0 && !visited[nextX][nextY]) {
     
                    visited[nextX][nextY] = true;
                    q.push(make_pair(nextX, nextY));
                }
            }
        }
    }

    return 0;
}

시공 복잡 도 O (m n) O (mn) O (mn).