DP is justice,DFS and BFS are heretical!


  • 0

    My English is very poor.This is my blog:blog.I will explain my algorithm in Chinese.
    First glance at the subject,I thought I can and I must resolve it by DP.

     /**
    	 * @param matrix
    	 * @return
    	 */
    	public int[][] updateMatrix(int[][] matrix) {
    		int h = matrix.length;
    		int w = matrix[0].length;
    		int[][] res = new int[h][w];
    		int MAX = 10000;
    		for (int i = 0; i < h; i++) {
    			for (int j = 0; j < w; j++) {
    				if (matrix[i][j] > 0) {
    					int leftVal = j == 0 ? MAX : res[i][j - 1] + 1;
    					int upVal = i == 0 ? MAX : res[i - 1][j] + 1;
    					res[i][j] = Math.min(leftVal, upVal);
    				}
    			}
    		}
    		for (int i = h - 1; i >= 0; i--) {
    			for (int j = w - 1; j >= 0; j--) {
    				if (matrix[i][j] > 0) {
    					int rightVal = j == w - 1 ? MAX : res[i][j + 1] + 1;
    					int downVal = i == h - 1 ? MAX : res[i + 1][j] + 1;
    					res[i][j] = Math
    							.min(res[i][j], Math.min(rightVal, downVal));
    				}
    			}
    		}
    		return res;
    	}
    

    First,foreach the matrix from left to right,from up to down.
    If matrix[i][j] is 0,the res[i][j] shoule be 0 ,too.
    Then res[i][j]=min([res[i-1][j],res[i][j-1]).
    Second,foreach the matrix from down to up,from right to left.
    If matrix[i][j] is 0,the res[i][j] shoule be 0 ,too.
    Then res[i][j]=min(res[i][j],min([res[i+1][j],res[i][j+1]))

    Tag:Why I define max=10000?At first I use Integer.MAX_VALUE.But sometimes it will be overflow.Just like MAX_VALUE+1.Besides that,he number of elements of the given matrix will not exceed 10,00.So I define max equals 10000.


Log in to reply
 

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