• API
• FAQ
• Tools
• Archive
SHARE
TWEET

# Untitled

a guest Jan 19th, 2020 77 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)){
35.                     if(!grid[ni][nj])
36.                         q.push({{ni,nj,node.k}, distance+1});
37.                     else if(grid[ni][nj] == 1 && node.k)
38.                         q.push({{ni,nj,node.k-grid[ni][nj]}, distance+1});
39.                 }
40.             }
41.         }
42.         return -1;
43.     }
44. };
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.
Top