BinarySearch - Escape-Maze

[https://binarysearch.com/problems/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>& matrix) { m = matrix.size(), n = matrix[0].size(); if (matrix[0][0] == 1 || matrix[m - 1][n - 1] == 1) return -1; queue, 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; } ```