Java BFS (some sort of flooding)


  • 0
    V
    class Solution {
        private int MAX = Integer.MAX_VALUE;
        int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        
        public int[][] updateMatrix(int[][] M) {
            int m = M.length, n = M[0].length;
            int[][] U = new int[m][n];
            
            Queue<int[]> q = new LinkedList<>();
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (M[i][j] != 0) U[i][j] = MAX;
                    else q.offer(getArray(i, j));
                }
            }
            
            int dist = 0;
            while(!q.isEmpty()) {
                Queue<int[]> next = new LinkedList<>();
                while (!q.isEmpty()) {
                    int[] one = q.poll();
                    for (int[] d : directions) {
                        int r = one[0] + d[0], c = one[1] + d[1];
                        if (isValid(U, r, c)) {
                            U[r][c] = dist + 1;
                            next.offer(getArray(r, c));
                        }
                    }
                }
                q = next;
                dist++;
            }
            
            return U;
        }
        
        int[] getArray(int i, int j) {
            int[] A = new int[2];
            A[0] = i;
            A[1] = j;
            return A;
        }
        
        boolean isValid(int[][] A, int r, int c) {
            return (r >= 0 && r < A.length && c >= 0 && c < A[0].length && A[r][c] == MAX);
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.