286. Walls and Gates
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.
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
First try dfs.
public class Solution {
static int EMPTY = 2147483647;
public void wallsAndGates(int[][] rooms) {
if(rooms == null || rooms.length == 0) return;
boolean 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] == 0){
dfs(rooms, i, j, visited, 0);
}
}
}
}
private void dfs(int[][] rooms, int x, int y, boolean[][] visited, int dis){
if(x < 0 || x >= rooms.length
|| y < 0 || y >= rooms[0].length || rooms[x][y] == -1)
return;
if(visited[x][y] || dis > rooms[x][y]) return;
rooms[x][y] = Math.min(rooms[x][y], dis);// since a room is already 0,
// in first level, there is no set really.
visited[x][y] = true;// to avoid loop.
dfs(rooms, x+1, y, visited, dis+1);
dfs(rooms, x-1, y, visited, dis+1);
dfs(rooms, x, y+1, visited, dis+1);
dfs(rooms, x, y-1, visited, dis+1);
visited[x][y] =false;
}
}
the visited array is to avoid loop, which can be done by checking dis > rooms[x][y]
Why dis > rooms[x][y] should return.
// NO VISITED ARRAY SOLUTION.
public class Solution {
static int EMPTY = 2147483647;
public void wallsAndGates(int[][] rooms) {
if(rooms == null || rooms.length == 0) return;
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 x, int y, int dis){
if(x < 0 || x >= rooms.length
|| y < 0 || y >= rooms[0].length || rooms[x][y] == -1)
return;
if( dis > rooms[x][y]) return;
// don't really need the min methods, if it is 0 ,then only show once.
rooms[x][y] = Math.min(rooms[x][y], dis);// since a room is already 0,
// in first level, there is no set really.
dfs(rooms, x+1, y, dis+1);
dfs(rooms, x-1, y, dis+1);
dfs(rooms, x, y+1, dis+1);
dfs(rooms, x, y-1, dis+1);
}
}
BFS classic
public class Solution {
public void wallsAndGates(int[][] rooms) {
if(rooms == null || rooms.length == 0 || rooms[0].length ==0) return;
for(int i =0 ; i< rooms.length; i++){
for(int j =0; j< rooms[0].length; j++){
if(rooms[i][j] == 0 ){
bfs(rooms, i, j);
}
}
}
}
private void bfs(int[][]rooms, int x, int y){
int[][] neighbor = {{1,0},{-1,0},{0,1},{0,-1}};
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{x,y});
boolean[][] visited = new boolean[rooms.length][rooms[0].length];
int dis = 0;
while(!queue.isEmpty()){
int size = queue.size();
for(int i =0; i< size; i++){
int[] top = queue.poll();
rooms[top[0]][top[1]] = Math.min(rooms[top[0]][top[1]], dis);
for(int j=0; j< 4;j++){
int k = top[0] + neighbor[j][0];
int l = top[1] + neighbor[j][1];
if(k>=0 && l>=0 && k< rooms.length && l < rooms[0].length && !visited[k][l] && rooms[k][l] > 0){
visited[k][l] = true;
queue.offer(new int[]{k,l});
}
}
}
dis++;
}
}
}
A better bfs solution.
public class Solution {
public void wallsAndGates(int[][] rooms) {
if(rooms == null || rooms.length == 0) return;
int[][] dir = new int[][]{{0,1},{0,-1},{1,0},{-1,0}};
class Pair{
int x;
int y;
Pair(int _x, int _y){
x = _x;
y = _y;
}
};
Queue<Pair> queue = new LinkedList<>();
for(int i= 0; i< rooms.length; i++){
for(int j =0; j< rooms[0].length; j++){
if(rooms[i][j] == 0){
queue.offer(new Pair(i,j));
}
}
}
while(!queue.isEmpty()){
Pair p = queue.poll();
for(int[] d : dir){
int x = p.x + d[0];
int y = p.y + d[1];
if(x <0 || x >= rooms.length || y <0 || y>= rooms[0].length
|| rooms[x][y] <= rooms[p.x][p.y] + 1)
continue;
rooms[x][y] = rooms[p.x][p.y] + 1;
queue.offer(new Pair(x,y));
}
}
}
}
without using class is actually slower than using it.
public class Solution {
public void wallsAndGates(int[][] rooms) {
if(rooms == null || rooms.length == 0) return;
int m = rooms.length;
int n = rooms[0].length;
int[][] dir = new int[][]{{0,1},{0,-1},{1,0},{-1,0}};
Queue<Integer> queue = new LinkedList<>();
for(int i= 0; i< rooms.length; i++){
for(int j =0; j< rooms[0].length; j++){
if(rooms[i][j] == 0){
queue.offer(i*n + j);
}
}
}
while(!queue.isEmpty()){
int p = queue.poll();
int px = p / n;
int py = p % n;
for(int[] d : dir){
int x = px + d[0];
int y = py + d[1];
if(x <0 || x >= rooms.length || y <0 || y>= rooms[0].length
|| rooms[x][y] <= rooms[px][py] + 1)
continue;
rooms[x][y] = rooms[px][py] + 1;
queue.offer(x*n + y);
}
}
}
}