BFS (AtCoder)

Solution by dudu — 100 pts

Code / Notes

// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N, M;
    cin >> N >> M;

    int si, sj;
    cin >> si >> sj;
    si--, sj--;

    int ei, ej;
    cin >> ei >> ej;
    ei--, ej--;

    vector<string> S(N);
    for (auto &x : S) cin >> x;

    vector<vector<int>> D(N, vector<int>(M, -1));
    queue<pair<int, int>> Q;
    Q.push({si, sj});

    while (not Q.empty()) {
        pair<int, int> v = Q.front();
        int x = v.first, y = v.second;
        Q.pop();
        if (S[x-1][y] == '.' && D[x-1][y] == -1) {
            D[x-1][y] = D[x][y] + 1;
            Q.push({x-1, y});
        }
        if (S[x+1][y] == '.' && D[x+1][y] == -1) {
            D[x+1][y] = D[x][y] + 1;
            Q.push({x+1, y});
        }
        if (S[x][y-1] == '.' && D[x][y-1] == -1) {
            D[x][y-1] = D[x][y] + 1;
            Q.push({x, y-1});
        }
        if (S[x][y+1] == '.' && D[x][y+1] == -1) {
            D[x][y+1] = D[x][y] + 1;
            Q.push({x, y+1});
        }
    }

    cout << D[ei][ej]+1 << endl;
}

Last updated 1 month ago

« Back to problem