LeetCode 286 Walls and Gates

思路

思路1：暴力搜索，对每个空房间(INF)进行bfs，不过此时的bfs应该是每次向队列中加下一层的元素而不是单个元素，否则深度会算错。
时间复杂度O($n^2?m^2$), 空间复杂度O($n?m$)

思路2:
思路1为多源多终点，可以转化为单源多终点（增加一个超级源，最短路常用套路）：从所有的门开始搜索，这样可以避免思路1中重复经过某些空房间。
在实现的时候忽略了超级源，直接在bfs之前将所有的门加入队列中。
时间复杂度O($n?m$), 空间复杂度O($n?m$)

代码

这里放的是思路2的代码

public class Solution {
    /*** @param rooms: m x n 2D grid* @return: nothing*/public void wallsAndGates(int[][] rooms) {
    // write your code hereif(rooms == null || rooms.length == 0 || rooms[0].length == 0)return;int row = rooms.length;int col = rooms[0].length;Queue<Integer> qx = new LinkedList<>();Queue<Integer> qy = new LinkedList<>();int[] dx = {
    0, 0, 1, -1};int[] dy = {
    1, -1, 0, 0};// search from gatesfor(int i = 0; i < row; i++) {
    for(int j = 0; j < col; j++) {
    if(rooms[i][j] == 0) {
    qx.offer(i);qy.offer(j);}}}// bfs: 从所有的0开始搜索while(!qx.isEmpty()) {
    int cx = qx.poll();int cy = qy.poll();for(int i = 0; i < 4; i++) {
    int nx = cx + dx[i];int ny = cy + dy[i];if(0 <= nx && nx < row && 0 <= ny && ny < col && rooms[nx][ny] == Integer.MAX_VALUE) {
    qx.offer(nx);qy.offer(ny);rooms[nx][ny] = rooms[cx][cy] + 1;}}}}
}