蹲在马桶看算法（Day6—LeetCode之NO.542 “01”矩阵）

题目：

给一个由0和1组成的矩阵，计算每个元素到最近0的距离。（说明：对角线之间最小距离为2）

个人思路：首先0到0的距离为0。然后做两次遍历，第一次遍历从左上角开始，让每一个元素跟其“靠左、靠上”的比较，获得最小距离，第二次遍历从右下角开始，让每一个元素跟其“靠右、靠下”的比较，获得最小距离。最后取两次遍历的中的较小值就是要求的结果。

	public int[][] updateMatrix(int[][] matrix) {
		if (matrix.length==0||matrix[0].length==0) {
			return matrix;
		}
		int[][] ans=new int[matrix.length][matrix[0].length];
		int range=matrix.length*matrix[0].length;
		for (int i = 0; i < matrix.length; i++) {
			for (int j = 0; j < matrix[0].length; j++) {
				//0——0的距离最近
				if (matrix[i][j]==0) {
					ans[i][j]=0;
				}else {
					int upCell=i>0?ans[i-1][j]:range;
					int leftCell=j>0?ans[i][j-1]:range;
					ans[i][j]=Math.min(upCell, leftCell)+1;
				}
			}
		}
		for (int i = matrix.length-1; i >-1; i--) {
			for (int j = matrix[0].length-1; j >-1; j--) {
				if (matrix[i][j]==0) {
					ans[i][j]=0;
				}else {
					int downCell=i<matrix.length-1?ans[i+1][j]:range;
					int rightCell=j<matrix[0].length-1?ans[i][j+1]:range;
					ans[i][j]=Math.min(Math.min(downCell, rightCell)+1, ans[i][j]);
				}
			}
		}
		return ans;
	}
	public static void main(String[] args) {
		int[][] arr= {{1,0,0},{1,1,1},{1,1,1}};
		int[][] ans=new ZeroOneMatrix().updateMatrix(arr);
		for (int i = 0; i < ans.length; i++) {
			for (int j = 0; j < ans[0].length; j++) {
				System.out.print(ans[i][j]+" ");
			}
			System.out.println();
		}
	}