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 value231 - 1 = 2147483647
to representINF
as you may assume that the distance to a gate is less than2147483647
.
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
.
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
典型的BFS,注意的是需要从所有0的位置同时开始走
O(m * n), m n 为2维数组的长宽。因为一个INF的点最多只被走一次
class Solution { public void wallsAndGates(int[][] rooms) { Queue<Pair> que = getQueue(rooms); fillRooms(rooms, que); } private void fillRooms(int[][] rooms, Queue<Pair> que) { int[][] coord = {{1,0}, {-1,0}, {0,1}, {0,-1}}; while (!que.isEmpty()) { Pair top = que.poll(); for (int[] arr : coord) { int r = top.row + arr[0]; int c = top.col + arr[1]; if (r >= 0 && r < rooms.length && c >= 0 && c < rooms[0].length && rooms[r][c] == 2147483647) { rooms[r][c] = rooms[top.row][top.col] + 1; que.add(new Pair(r, c)); } } } } private Queue<Pair> getQueue(int[][] rooms) { Queue<Pair> que = new LinkedList<>(); for (int i = 0; i < rooms.length; i++) { for (int j = 0; j < rooms[0].length; j++) { if (rooms[i][j] == 0) { que.add(new Pair(i, j)); } } } return que; } } class Pair{ public int row; public int col; public Pair(int row, int col) { this.row = row; this.col = col; } }
No comments:
Post a Comment