Java Brute Force Solution


  • 0
    W

    The idea is simple, just check every cell to update its value from its neighbors, until no cell get updated;

    public void wallsAndGates(int[][] rooms) {
    	int INF = 2147483647;
    
    	int m = rooms.length;
    	if (m == 0) {
    		return;
    	}
    	int n = rooms[0].length;
    	if (n == 0) {
    		return;
    	}
    
    	boolean hasUpdate = true;
    	while (hasUpdate) {
    		hasUpdate = false;
    		for (int i = 0; i < m; i++) {
    			for (int j = 0; j < n; j++) {
    				int val = rooms[i][j];
    				if (val <= 0) {
    					continue;
    				}
    
    				int left = -1;
    				if (j > 0) {
    					left = rooms[i][j - 1];
    				}
    
    				if (left >= 0 && left < INF && left + 1 < val) {
    					val = left + 1;
    				}
    
    				int top = -1;
    				if (i > 0) {
    					top = rooms[i - 1][j];
    				}
    
    				if (top >= 0 && top < INF && top + 1 < val) {
    					val = top + 1;
    				}
    
    				int right = -1;
    				if (j < n - 1) {
    					right = rooms[i][j + 1];
    				}
    
    				if (right >= 0 && right < INF && right + 1 < val) {
    					val = right + 1;
    				}
    
    				int bottom = -1;
    				if (i < m - 1) {
    					bottom = rooms[i + 1][j];
    				}
    
    				if (bottom >= 0 && bottom < INF && bottom + 1 < val) {
    					val = bottom + 1;
    				}
    
    				if (val < rooms[i][j]) {
    					rooms[i][j] = val;
    					hasUpdate = true;
    				}
    			}
    		}
    
    	}
    }

Log in to reply
 

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