Java 37ms DFS with memoization


  • 0
    X

    The firstly thought is dynamic progrommaing, but I find it's difficult to init dp.
    Then I use dfs

    private static final int[][] dir = {{-1 , 0}, {1, 0}, {0, 1}, {0, -1}};
    
    public List<List<Integer>> updateMatrix(List<List<Integer>> matrix) {
        	if(matrix == null || matrix.get(0) == null){
            	return matrix;
            }
            int m = matrix.size();
            int n = matrix.get(0).size();
            int[][] memorization = new int[m][n];
            boolean[][] find = new boolean[m][n];
            for (int i = 0; i < m; i++) {
    			for (int j = 0; j < n; j++) {
    				memorization[i][j] = Integer.MAX_VALUE;
    			}
    		}
            for(int i = 0; i < m; i++){
        		for(int j = 0; j < n; j++){
        			if(matrix.get(i).get(j) != 0){
        				matrix.get(i).set(j, dfs(matrix, i, j, m , n, memorization, find));
        			}
        		}
            }
            return matrix;
        }
    
    public int dfs(List<List<Integer>> matrix, int x, int y, int m, int n, 
        		int[][] memorization, boolean[][] find){
        	if(x < 0 || x >= m || y < 0 || y >= n){
    			return 0;
    		}
        	//think the testCase   0 1 1  1  1  1  1  0
        	if(memorization[x][y] != Integer.MAX_VALUE){
        		for(int k = 0; k < dir.length; k++){
        			int i = x + dir[k][0];
        			int j = y + dir[k][1];
        			if(i < 0 || i >= m || j < 0 || j >= n){
        				continue;
        			}
                            //adjacent difference is more than 1;
        			if(memorization[i][j] <= memorization[x][y] - 2){
        				memorization[x][y] = memorization[i][j] + 1;
        			}
        		}
        		return memorization[x][y];
        	}
        	
        	if(matrix.get(x).get(y) == 0){
        		memorization[x][y] = 0;
        		return 0;
        	}
        	int min = Integer.MAX_VALUE;
        	find[x][y] = true;
        	for(int k = 0; k < dir.length; k++){
    			int i = x + dir[k][0];
    			int j = y + dir[k][1];
    			if(i < 0 || i >= m || j < 0 || j >= n){
    				continue;
    			}
    			if(matrix.get(i).get(j) == 0){
    				memorization[i][j] = 0;
    				memorization[x][y] = 1;
    				find[x][y] = false;
    				return 1;
    			}
    		}
        	for(int k = 0; k < dir.length; k++){
    			int i = x + dir[k][0];
    			int j = y + dir[k][1];
    			if(i < 0 || i >= m || j < 0 || j >= n || find[i][j]){
    				continue;
    			}
    			min = Math.min(min, dfs(matrix, i , j, m, n, memorization, find) + 1);
    		}
        	find[x][y] = false;
        	memorization[x][y] = min;
        	return min;
        }
    

    I don't know if there is another case can't pass? If you find it, please tell me!


Log in to reply
 

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