Thinking process - BFS

Similar to find the shortest path => BFS

Add all gates to a queue first, then update its neighbors (INFs) and add updated elements positions into queue, until no INFs are left.

Mistakes

How to avoid infinite loop?

• only update the INF position, which follow the BFS rule

Time Complexity

O (mn)

public class Solution {
    public void wallsAndGates(int[][] rooms) {
        if (rooms == null || rooms.length == 0) {
            return;
        }
        int n = rooms.length, m = rooms[0].length;
        Queue<Integer> q = new LinkedList<>();

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (rooms[i][j] == 0) {
                    q.offer(i * m + j);
                }
            }
        }

        int[] dx = {-1, 0, 1, 0};
        int[] dy = {0, 1, 0, -1};

        while (!q.isEmpty()) {
            int num = q.poll();
            int x = num / m, y = num % m;

            for (int i = 0; i < dx.length; ++i) {
                if (x + dx[i] < 0 || x + dx[i] >= n || y + dy[i] < 0 || y + dy[i] >= m || 
                        rooms[x + dx[i]][y + dy[i]] != Integer.MAX_VALUE) continue;
                rooms[x + dx[i]][y + dy[i]] = rooms[x][y] + 1;
                q.offer((x + dx[i]) * m + y + dy[i]);
            }
        }
    }
}

Thinking process - DFS

if the value is smaller than given, return

Time Complexity

public class Solution {
    private static final int[][] DX_DY = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
    public void wallsAndGates(int[][] rooms) {
        for (int i = 0; i < rooms.length; ++i) {
            for (int j = 0; j < rooms[0].length; ++j) {
                if (rooms[i][j] == 0) dfsHelper(rooms, i, j, 0);
            }
        }
    }

    private void dfsHelper(int[][] rooms, int i, int j, int value) {
        if (i < 0 || i >= rooms.length || j < 0 || j >= rooms[0].length || rooms[i][j] < value) return;

        rooms[i][j] = value;

        for (int k = 0; k < DX_DY.length; ++k) {
            dfsHelper(rooms, i + DX_DY[k][0], j + DX_DY[k][1], value + 1);
        } 
    }
}