1.题目描述2.解法
2.1 深度优先搜索（DFS）递归实现2.2 广度优先搜索（BFS）2.3 动态规划（DP）
1.题目描述给定一个由 0 和 1 组成的矩阵 mat ，请输出一个大小相同的矩阵，其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。
两个相邻元素间的距离为 1 。
示例1：
输入：mat = [[0,0,0],[0,1,0],[0,0,0]]
输出：[[0,0,0],[0,1,0],[0,0,0]]
示例2：
输入：mat = [[0,0,0],[0,1,0],[1,1,1]]
输出：[[0,0,0],[0,1,0],[1,2,1]]
提示：
m == mat.length
n == mat[i].length
1 <= m, n <= 104
1 <= m * n <= 104
mat[i][j] is either 0 or 1.
mat 中至少有一个 0
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/01-matrix
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
因为0和靠近0的1是不需要改变的。
所以首先将矩阵初始化，将需要计算距离的点全初始化为最大值。
之后通过递归，从1开始向离0远的地方寻找还未计算过距离的点同时更新最短距离。
class Solution {
int dx[] = {1,0,0,-1};//左右移动
int dy[] = {0,1,-1,0};//上下移动
int m,n;
public int[][] updateMatrix(int[][] mat) {
m = mat.length;
if(m==0){
return mat;
}
n = mat[0].length;
for(int i=0;i=0&&mx=0&&my=0&&mx=0&&mymat[x][y]+1){
mat[mx][my] = mat[x][y] +1;
dfs(mat,mx,my);
}
}
}
}
}
2.2 广度优先搜索（BFS）
广度优先搜索需要用到队列Java队列，可以从这里复习。
广度优先搜索官方题解讲的很好。
我的理解就是通过队列管理计算过距离的点，计算过的点就放入队列，通过while循环队列从0向外开始计算，先从队列中取出一个点计算上下左右如果有计算过的点就放入队列，并记录一下已经访问过的点，防止进入死循环。
当队列为空时说明了所有的点都已经计算过了。
代码如下
class Solution {
int dx[]={1,0,0,-1};//左右移动
int dy[]={0,1,-1,0};//上下移动
int m,n;
public int[][] updateMatrix(int[][] mat) {
m = mat.length;
if(m==0){
return mat;
}
n = mat[0].length;
int[][] newMat = new int[m][n];//存储计算过的距离
boolean[][] seen = new boolean[m][n];//存储是否访问过该点
Queue queue = new linkedList();//用二维队列存储需要访问四周的额点
for(int i=0;i=0&&mx=0&&my
2.3 动态规划（DP）
动态规划最重要的就是状态转移方程。
我的理解就是从终点向前走一步离起点更近，而终点可以用一个值+更近的点表示。
以下是我的理解，相当于官方题解的缩略版。
从1到0，一共有上下左右四个方向。
而上下和左右结合，共有四种方法。
只有 水平向左移动 和 竖直向上移动；只有 水平向左移动 和 竖直向下移动；只有 水平向右移动 和 竖直向上移动；只有 水平向右移动 和 竖直向下移动。
假如1在0的右下方，则1需要向左移动和向上移动，此时的状态转移方程就是。
可以类推出来剩下的方程。
代码如下：
class Solution {
public int[][] updateMatrix(int[][] mat) {
int m = mat.length;
if(m==0){
return mat;
}
int n = mat[0].length;
int [][]newMat = new int[m][n];
for(int i=0;i=0;j--){
if(i-1>=0){
newMat[i][j]=Math.min(newMat[i-1][j]+1,newMat[i][j]);
}
if(j+1=0){
newMat[i][j]=Math.min(newMat[i-1][j]+1,newMat[i][j]);
}
if(j-1>=0){
newMat[i][j]=Math.min(newMat[i][j-1]+1,newMat[i][j]);
}
}
}
//向左向下
for(int i=m-1;i>=0;i--){
for(int j=0;j=0){
newMat[i][j]=Math.min(newMat[i][j-1]+1,newMat[i][j]);
}
}
}
//向右向下
for(int i=m-1;i>=0;i--){
for(int j=n-1;j>=0;j--){
if(i+1 
