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

思路: 求矩阵中room到gate的最短距离这个题目用DFS 比较快。
DFS: 找的时候如果当前点的值大于idx的值,就是符合条件的点。
复杂度: 时间 MN4^K, 空间 4^N

public class Solution {
    public void wallsAndGates(int[][] rooms) {
        if (rooms == null || rooms.length == 0 || rooms[0] == null || 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) {
                    dfs(rooms, i, j, 0);
                }
            }
        }
    }

    public void dfs(int[][] rooms, int x, int y, int idx) {
        if (x < 0 || x >= rooms.length || y < 0 || y >= rooms[0].length || rooms[x][y] < idx) return;
        rooms[x][y] = idx;
        dfs(rooms, x + 1, y, idx + 1);
        dfs(rooms, x - 1, y, idx + 1);
        dfs(rooms, x, y + 1, idx + 1);
        dfs(rooms, x, y - 1, idx + 1);
    }
}

BFS的解

public class Solution {
    public class Point {
        int x;
        int y;
        int prevPos;
        public Point(int x, int y, int prevPos) {
            this.x = x;
            this.y = y;
            this.prevPos = prevPos;
        }
    }
    public int[] xDir = new int[]{-1, 0 , 1, 0};
    public int[] yDir = new int[]{0, 1, 0, -1};

    public void wallsAndGates(int[][] rooms) {
        if (rooms == null || rooms.length == 0 || rooms[0] == null || 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);
                }
            }
        }
    }

    public void bfs(int[][] rooms, int x, int y) {
        if (x < 0 || x >= rooms.length || y < 0 || y >= rooms[0].length) return;
        ArrayDeque<Point> queue = new ArrayDeque<>();
        queue.offer(new Point(x, y, 0)); // add the start point to the queue
        while(!queue.isEmpty()) {
            Point point = queue.pop(); // dequeue and check 

            // explore 4 directions
            for (int i = 0; i < 4; i++) {
                int newX = point.x + xDir[i];
                int newY = point.y + yDir[i];
                Point newPoint = new Point(newX, newY, point.prevPos);
                if (shouldExplore(newPoint, rooms)) {
                    newPoint.prevPos += 1;
                    rooms[newX][newY] = newPoint.prevPos;
                    queue.offer(newPoint);
                }
            }
        }
    }

    public boolean shouldExplore(Point p, int[][] rooms) {
        if (p.x < 0 || p.x >= rooms.length || p.y < 0 || p.y >= rooms[0].length || rooms[p.x][p.y] < p.prevPos || rooms[p.x][p.y] == -1 ) return false;
        return true;
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s