wkw

Posted on

# 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;
}
``````