It always gets TLE, and for DFS solution, it is stackoverflow.
I guess most testcases contain too many empty rooms compared to gates.
Has anyone tried using BFS or DFS starting from empty room instead of gate

Hi pinkfloyda, I tried this, but got a TLE.
public class Solution { final int INF = 2147483647; boolean[][] visited; public void wallsAndGates(int[][] rooms) { if(rooms.length == 0) return; visited = new boolean[rooms.length][rooms[0].length]; for(int i = 0; i < rooms.length; i++) { for(int j = 0; j < rooms[0].length; j++) { if(rooms[i][j] == INF){ visited = new boolean[rooms.length][rooms[0].length]; rooms[i][j] = getDistance(rooms, i, j, 0, rooms[i][j], visited); } } } } private int getDistance(int[][] rooms, int i, int j, int distance, int shortest, boolean[][] visited) { int curShort = shortest; if(i < 0  i >= rooms.length  j < 0  j >= rooms[0].length  rooms[i][j] == 1  visited[i][j]) { return INF; } visited[i][j] = true; if(rooms[i][j] == 0){ return distance; } int result = Math.min(Math.min(getDistance(rooms, i+1, j, distance+1, shortest,visited),getDistance(rooms, i1, j, distance+1, shortest,visited)),Math.min(getDistance(rooms, i, j+1, distance+1, shortest,visited),getDistance(rooms, i, j1, distance+1, shortest,visited))); visited[i][j] = false; return result; }

I cannot say for sure "much more empty rooms than gates" matters or not, I just feel it. For your case, if there are more gates, I think it should be easier for each DFS path reach that gate and return the function early without stackoverflow. And also I came out with the case, just imagine almost all cells are empty rooms except the rightbottom corner is the gate.

finally I figured out the solution. We should prune the points that have been calculated before 
both in current recursion procedure and recursion procedure before.enter code here
public class Solution {
public final static int INF = 2147483647;public void wallsAndGates(int[][] rooms) { if(rooms == null  rooms.length == 0) return; int row = rooms.length; int col = rooms[0].length; boolean[][] visit = new boolean[row][col]; for(int i = 0; i < rooms.length; i++){ for(int j = 0; j < rooms[0].length; j++){ //We only need to calculate the distance for points with value of INF if(rooms[i][j] == INF){ rooms[i][j] = dfs(i, j, rooms, visit); } } } } / //dfs will return the shortest distance from gate to current point(x, y) private int dfs(int x, int y, int[][] rooms, boolean[][] visit){ int row = rooms.length; int col = rooms[0].length; //invalid point should not interrupt calculation for min, thus return INF if(x < 0  x>= row  y < 0  y >= col  rooms[x][y] == 1) return INF; //visited before(in current recursion procedure) if(visit[x][y]) return rooms[x][y]; visit[x][y] = true; if(rooms[x][y] == 0){ return 0; } //calculated before(not in current recursion procedure) if(rooms[x][y] > 0 && rooms[x][y] < INF){ return rooms[x][y]; } int[] surroundx = new int[]{1, 1, 0, 0}; int[] surroundy = new int[]{0, 0, 1, 1}; int min = rooms[x][y]; for(int i = 0; i < 4; i++){ int nextX = x + surroundx[i]; int nextY = y + surroundy[i]; //min is the min distance among the surrounding 4 points to gates min = Math.min(min, dfs(nextX, nextY, rooms, visit)); } visit[x][y] = false; if(min == INF) return INF; //min is the min distance among the surrounding 4 points to gate, thus min distance of current point to gate is min + 1 else return min + 1; }
}