Walls And Gates | Leetcode 286 solution
You are given a m x n 2D grid initialized with these three possible values.
-1
- A wall or an obstacle.0
- A gate.INF
- Infinity means an empty room. We use the value 231 - 1 = 2147483647
to represent INF
as you may assume that the distance to a gate is less than 2147483647
.
Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, it should be filled with INF
.
Example:
Given the 2D grid:
INF -1 0 INF
INF INF INF -1
INF -1 INF -1
0 -1 INF INF
After running your function, the 2D grid should be:
3 -1 0 1
2 2 1 -1
1 -1 2 -1
0 -1 3 4
Solution :
#include <bits/stdc++.h> vector<vector<int>> wallsAndGates(vector<vector<int>> &a, int n, int m) { // Write your code here. queue<pair<int , int>>q; // vector<pair<int, int>>vect; vector<vector<int>>visited(n , vector<int>(m , 0));
for(int i =0; i < n ; i++ ) { for(int j =0; j < m ; j++) { if(a[i][j] == 0) { visited[i][j] =1; q.push({i, j}); } } } // visited[vect[l].first][vect[l].second] =1; while(!q.empty()) { auto node = q.front(); int i = node.first; int j = node.second; q.pop(); int x[4] = {0 , 1 , 0, -1}; int y[4] = {1 , 0 , -1 , 0}; for(int k =0 ; k < 4 ; k++) { int row = i + x[k]; int col = j + y[k]; if(row >=0 && row < n && col >=0 && col < m && !visited[row][col] && a[row][col] != -1 && a[row][col] != 0) { visited[row][col] = 1; a[row][col] = min(a[row][col], a[i][j] +1 ); q.push({row, col}); } } }
return a; } |
Comments
Post a Comment