DP is justice,DFS and BFS are heretical！

• 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.

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