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

答案

又臭又长又TLE的答案

class Coord {
        int x;
        int y;
        public Coord(int x, int y) { this.x = x; this.y = y;}
    }

    int[][] delta = {{-1, 0},{1, 0},{0, 1},{0, -1}};
    public void bfs(int[][] rooms, int i, int j) {
        Queue q = new LinkedList();
        boolean[][] visited = new boolean[rooms.length][rooms[0].length];
        Coord source = new Coord(i, j);

        // Use queue to perform bfs search, if visited, mark, if is gate, mark number
        int curr_distance = 1;
        q.offer(source);
        while(!q.isEmpty()) {
            int qsize = q.size();

            for(int m = 0; m < qsize; m++) {
                Coord curr = q.poll();
                visited[curr.x][curr.y] = true;
                for(int k = 0; k < 4; k++) {
                    Coord c = new Coord(curr.x + delta[k][0], curr.y + delta[k][1]);

                    if(!(c.x < 0 || c.x >= rooms.length || c.y < 0 || c.y >= rooms[0].length || rooms[c.x][c.y] == -1) && !visited[c.x][c.y])
                        q.offer(c);
                    else
                        continue;
                    if(rooms[c.x][c.y] == 0) {
                        rooms[source.x][source.y] = curr_distance;
                        return;
                    }
                }
            }

            curr_distance++;
        }

    }
    public void wallsAndGates(int[][] rooms) {
        for(int i = 0; i < rooms.length; i++) {
            for(int j = 0; j < rooms[0].length; j++) {
                int shortest = 0;
                if(rooms[i][j] == Integer.MAX_VALUE) {
                    bfs(rooms, i, j);
                }
            }
        }
    }

优雅思路简单的答案

class Solution {
    int[][] delta = {{-1, 0},{1, 0},{0, 1},{0, -1}};

    public void wallsAndGates(int[][] rooms) {
        Queue q = new LinkedList();
        for(int i = 0; i < rooms.length; i++) {
            for(int j = 0; j < rooms[0].length; j++) {
                if(rooms[i][j] == 0) {
                    q.offer(new int[]{i, j});
                }
            }
        }

        while(!q.isEmpty()) {
            int[] curr = q.poll();
            for(int i = 0; i < 4; i++) {
                int[] nber = new int[]{curr[0] + delta[i][0], curr[1] + delta[i][1]};
                if (nber[0] < 0 || nber[0] >= rooms.length || nber[1] < 0 || nber[1] >= rooms[0].length || rooms[nber[0]][nber[1]] != Integer.MAX_VALUE)
                    continue;
                rooms[nber[0]][nber[1]] = rooms[curr[0]][curr[1]] + 1;
                q.offer(nber);
            }
        }
    }
}

你可能感兴趣的