This content originally appeared on DEV Community and was authored by Wing-Kam WONG
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;
}
This content originally appeared on DEV Community and was authored by Wing-Kam WONG
Wing-Kam WONG | Sciencx (2021-10-02T02:33:35+00:00) BinarySearch – Escape-Maze. Retrieved from https://www.scien.cx/2021/10/02/binarysearch-escape-maze/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.