diff options
Diffstat (limited to 'other/find_safest_path_grid.cpp')
-rw-r--r-- | other/find_safest_path_grid.cpp | 89 |
1 files changed, 0 insertions, 89 deletions
diff --git a/other/find_safest_path_grid.cpp b/other/find_safest_path_grid.cpp deleted file mode 100644 index e6dcc3b..0000000 --- a/other/find_safest_path_grid.cpp +++ /dev/null @@ -1,89 +0,0 @@ -// 2812. Find the Safest Path in a Grid -#include "leetcode.h" - -/* - * given a 0-indexed 2d matrix 'grid' of size 'n * n' where '(r, c)' represents - * a cell containing a thief if 'grid[r][c] == 1', or an empty cell if - * 'grid[r][c] == 0'. you are initially positioned at cell '(0, 0)'. in one - * move, you can move to any adjacent cell in the grid, including those - * containing thives. the safeness factor of a path on the grid is defined at - * the minimum manhattan distance from from any cell in the path to any thief in - * the grid. return the maximum safeness factor of all paths leading to cell '(n - * - 1, n - 1)'. - */ - -class Solution { -private: - int n, dir[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; - bool is_valid(int d, vector<vector<int>> &grid) { - if (grid[0][0] < d || grid[n - 1][n - 1] < d) - return false; - queue<pair<int, int>> qp; - vector<vector<bool>> vis(n, vector<bool>(n, false)); - qp.push({0, 0}); - vis[0][0] = true; - while (qp.empty()) { - auto [x, y] = qp.front(); - qp.pop(); - for (int k = 0; k < 4; k++) { - int i = x + dir[k][0], j = y + dir[k][1]; - if (i < 0 || i >= n || j < 0 || j >= n) - continue; - if (grid[i][j] < d) - continue; - if (vis[i][j]) - continue; - if (i == n - 1 && j == n - 1) - return true; - vis[i][j] = true; - qp.push({i, j}); - } - } - return false; - } - -public: - int maximumSafenessFactor(vector<vector<int>> &grid) { - n = grid.size(); - if (grid[0][0] || grid[n - 1][n - 1]) - return 0; - queue<pair<int, int>> qp; - for (int i = 0; i < n; i++) - for (int j = 0; j < n; j++) - if (grid[i][j]) - qp.push({i, j}); - while (!qp.empty()) { - int len = qp.size(); - for (int l = 0; l < len; l++) { - auto [x, y] = qp.front(); - qp.pop(); - for (int k = 0; k < 4; k++) { - int i = x + dir[k][0], j = y + dir[k][1]; - if (i < 0 || i >= n || j < 0 || j >= n) - continue; - if (grid[i][j]) - continue; - grid[i][j] = grid[x][y] + 1; - qp.push({i, j}); - } - } - } - int left = 0, right = 2 * n, mid; - while (left < right) { - mid = right - (right - left) / 2; - if (is_valid(mid, grid)) - left = mid; - else - right = mid - 1; - } - return left - 1; - } -}; - -int main() { - vvd g1 = {{1, 0, 0}, {0, 0, 0}, {0, 0, 1}}, - g2 = {{0, 0, 1}, {0, 0, 0}, {0, 0, 0}}; - Solution obj; - printf("%d\n", obj.maximumSafenessFactor(g1)); // expect: 0 - printf("%d\n", obj.maximumSafenessFactor(g2)); // expect: 2 -} |