SHARE
TWEET

Untitled

a guest Jan 19th, 2020 81 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. struct LevelNode {
  2.     int i;
  3.     int j;
  4.     int k;
  5. };
  6.  
  7.  
  8. class Solution {
  9.     bool isValid(int i, int j, int n, int m){
  10.         return i >= 0 && j >= 0 && i < n && j < m;
  11.     }
  12.  
  13. public:
  14.     int shortestPath(vector<vector<int>>& grid, int k) {  
  15.         int n = grid.size();
  16.         int m = n? grid[0].size() : 0;
  17.         int di[4] = {0, 0, 1, -1};
  18.         int dj[4] = {1, -1, 0, 0};
  19.         queue<pair<LevelNode, int>> q;
  20.         vector<vector<vector<int>>> vis(n, vector<vector<int>>(m, vector<int>(k+1)));
  21.         q.push({{0, 0, k},0});
  22.         while(q.size()){
  23.             LevelNode node = q.front().first;
  24.             int distance = q.front().second;
  25.             q.pop();
  26.             if(node.i == n-1 && node.j == m-1)
  27.                 return distance;
  28.             if(!isValid(node.i, node.j, n, m) || vis[node.i][node.j][node.k])
  29.                 continue;
  30.             vis[node.i][node.j][node.k] = 1;
  31.             for(int d = 0; d < 4; d++) {
  32.                 int ni = node.i + di[d];
  33.                 int nj = node.j + dj[d];
  34.                 if(isValid(ni, nj, n, m) && (!grid[ni][nj] || grid[ni][nj] == 1 && node.k))
  35.                     q.push({{ni,nj,node.k-grid[ni][nj]}, distance+1});
  36.             }
  37.         }
  38.         return -1;
  39.     }
  40. };
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top