Competitive Programming Solutions

abc151_d - Maze Master

29 Jan 2021 — Tags: bfs,graphs — URL

The problem basically asks to ask of the diameter of the graph represented by the board. We can get this number by launching a bfs from each cell to find the furthest reachable cell.

Time complexity: $O(n^4)$

Memory complexity: $O(n^2)$

Click to show code.

 

using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
using namespace std;
ll bfs(int i, int j, vector<string> &board)
{
    int h = (int)(board).size(), w = (int)(board[0]).size();
    vector<vector<bool>> visited(h, vector<bool>(w, 0));
    vector<vector<ll>> dist(h, vector<ll>(w, 1e9));
    queue<ii> frontier;
    frontier.emplace(i, j);
    visited[i][j] = true;
    dist[i][j] = 0;
    ll ans = 0;
    auto check = [&](int r, int c) {
        return board[r][c] != '#' and !visited[r][c];
    };
    auto visit = [&](int r, int c, ll d) {
        frontier.emplace(r, c);
        visited[r][c] = true;
        dist[r][c] = d;
        ans = max(ans, d);
    };
    while (not frontier.empty())
    {
        auto [r, c] = frontier.front();
        frontier.pop();
        if (check(r, c + 1))
            visit(r, c + 1, dist[r][c] + 1);
        if (check(r + 1, c))
            visit(r + 1, c, dist[r][c] + 1);
        if (check(r, c - 1))
            visit(r, c - 1, dist[r][c] + 1);
        if (check(r - 1, c))
            visit(r - 1, c, dist[r][c] + 1);
    }
    return ans;
}
ll solve(vector<string> board)
{
    int h = (int)(board).size() - 2, w = (int)(board[0]).size() - 2;
    ll ans = 0;
    for (int i = 1; i <= h; ++i)
        for (int j = 1; j <= w; ++j)
            if (board[i][j] != '#')
                ans = max(ans, bfs(i, j, board));
    return ans;
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int h, w;
    cin >> h >> w;
    vector<string> board(h + 2);
    board[0] = string(w + 2, '#');
    board[h + 1] = string(w + 2, '#');
    for (int i = 1; i <= h; ++i)
    {
        cin >> board[i];
        board[i] = "#" + board[i] + "#";
    }
    cout << solve(board) << endl;
    return 0;
}

Related posts