BinarySearch - Escape-Maze

https://binarysearch.com/problems/Escape-Maze

Problem

You are given a two dimensional integer matrix, representing a maze where 0 is an empty cell, and 1 is a wall. Given that you start at matrix[0][0], return the minimum number of squares it would take to get to matrix[R - 1][C - 1] where R and C are the number of rows and columns in the matrix.

If it's not possible, return -1.

Constraints

n, m ≤ 250 where n and m are the number of rows and columns in matrix

Solution

Use standard BFS.

Check if the matrix[0][0] and matrix[m-1][n-1] is 1 or not. If so, return -1.

Then we need a queue to store the coordinates and the local count.

Starting from (0,0), go for four directions and check if the target cell is valid or not. If so, update matrix[xx][yy] so that we won't visit it again and add it to the queue. If xx and yy reaches m-1 and n-1, check if the count is the minimal.

int ans = INT_MAX, m, n;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, -1, 0, 1};
bool ok(int i, int j) {
    return !(i < 0 || i > m - 1 || j < 0 || j > n - 1);
}
int solve(vector<vector<int>>& matrix) {
    m = matrix.size(), n = matrix[0].size();
    if (matrix[0][0] == 1 || matrix[m - 1][n - 1] == 1) return -1;
    queue<pair<pair<int, int>, int>> q;  // i, j, cnt
    q.push({{0, 0}, 1});
    matrix[0][0] = 1;
    while (!q.empty()) {
        auto p = q.front();
        q.pop();
        int x = p.first.first, y = p.first.second, cnt = p.second;
        if (x == m - 1 && y == n - 1) ans = min(ans, cnt);
        for (int i = 0; i < 4; i++) {
            int xx = x + dx[i], yy = y + dy[i];
            if (ok(xx, yy) && matrix[xx][yy] == 0) {
                matrix[xx][yy] = 1;
                q.push({{xx, yy}, cnt + 1});
            }
        }
    }
    return ans == INT_MAX ? -1 : ans;
}