Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class Solution {
- public:
- bool issafe(vector<vector<int>>& matrix, int i, int j) {
- return (i >= 0 && i < matrix.size() && j >= 0 && j < matrix[0].size() && matrix[i][j] == 0);
- }
- void solve(vector<vector<int>>& matrix, int i, int j, vector<vector<int>>& memo, int lencount, int& min_len) {
- if (i == matrix.size() - 1 && j == matrix[0].size() - 1) {
- min_len = min(min_len, lencount);
- return;
- }
- if (memo[i][j] != -1 && lencount >= memo[i][j]) {
- return;
- }
- memo[i][j] = lencount;
- vector<pair<int,int>> dir = {{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
- for (int k = 0; k < 8; k++) {
- int r = i + dir[k].first;
- int c = j + dir[k].second;
- if (issafe(matrix, r, c)) {
- solve(matrix, r, c, memo, lencount + 1, min_len);
- }
- }
- }
- int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
- if (grid[0][0] == 1 || grid[grid.size()-1][grid[0].size()-1] == 1) return -1;
- vector<vector<int>> memo(grid.size(), vector<int>(grid[0].size(), -1));
- int min_len = INT_MAX;
- solve(grid, 0, 0, memo, 1, min_len);
- if (min_len == INT_MAX) return -1;
- return min_len;
- }
- };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement