LeetCode [286] Walls and Gates

286. Walls and Gates

Medium

You are given a m x n 2D grid initialized with these three possible values.

1. -1 - A wall or an obstacle.
2. 0 - A gate.
3. 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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

class Solution { public: void wallsAndGates(vector<vector<int>>& rooms) { int m = rooms.size(); if(m==0) return; int n = rooms[0].size(); if(n==0) return; for(int i=0; i<m; ++i){ for(int j=0; j<n; ++j){ stack<pair<int, int>> stk; if(rooms[i][j]==0){ stk.push(pair<int, int>(i,j)); while(!stk.empty()){ int x = stk.top().first, y = stk.top().second; stk.pop(); if(x-1>=0 && rooms[x-1][y]>rooms[x][y]+1){rooms[x-1][y] = rooms[x][y]+1; stk.push(pair<int, int>(x-1,y));} if(x+1<m && rooms[x+1][y]>rooms[x][y]+1){rooms[x+1][y] = rooms[x][y]+1; stk.push(pair<int, int>(x+1,y));} if(y-1>=0 && rooms[x][y-1]>rooms[x][y]+1){rooms[x][y-1] = rooms[x][y]+1; stk.push(pair<int, int>(x,y-1));} if(y+1<n && rooms[x][y+1]>rooms[x][y]+1){rooms[x][y+1] = rooms[x][y]+1; stk.push(pair<int, int>(x,y+1));} } } } } } };

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

class Solution { int[][] dirs = new int[][]{{-1,0},{1,0},{0,-1},{0,1}}; int m, n; public void wallsAndGates(int[][] rooms) { m = rooms.length; if(m==0) return; n = rooms[0].length; for(int i=0; i<m; ++i){ for(int j=0; j<n; ++j){ if(rooms[i][j]==0){ dfs(rooms, i, j); } } } } void dfs(int[][] rooms, int i0, int j0){ for(int[] d : dirs){ int i = i0+d[0], j = j0+d[1]; if(i>=0 && i<m && j>=0 && j<n && rooms[i][j]!=-1){ if(rooms[i][j]>rooms[i0][j0]+1){ rooms[i][j] = rooms[i0][j0]+1; dfs(rooms, i, j); } } } } }