Leetcode/G家，F家 -- 286. Walls and Gates(Backtracking)

286. Walls and Gates(Backtracking)

• Difficulty: Medium

https://leetcode.com/problems/walls-and-gates/

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.

For 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

相关题： http://rainykat.blogspot.com/2017/01/leetcode-200-number-of-islandsback.html

思路: find all gates use dfs to traverse all surrounding pos, when reach wall, gate or confirm min distance, return;
Complexity: O(M*N) M: row length, N: col len (wortst case, only one gate all other rooms)
关键字： backtracking

public class Solution {
    public void wallsAndGates(int[][] rooms) {
        for (int i = 0; i < rooms.length; i++)
            for (int j = 0; j < rooms[0].length; j++)
                if (rooms[i][j] == 0){
                    dfs(rooms, i, j,0);
                }
    }

    private void dfs(int[][] rooms, int i, int j,int d) {
        if(i<0||i>=rooms.length||j>=rooms[0].length||j<0||rooms[i][j]<d)//ensure min dis + avoid wall 
            return;// <d: return wall + gate + ensure min distance
        rooms[i][j]=d;//i row,j col
        dfs(rooms, i - 1, j,d+1);
        dfs(rooms, i + 1, j,d+1);
        dfs(rooms, i, j - 1,d+1);
        dfs(rooms, i, j + 1,d+1);
    }
}