給定一個由 0 和 1 組成的矩陣，找出每個元素到最近的 0 的距離。
兩個相鄰元素間的距離為 1 。
示例 1:
輸入:
0 0 0
0 1 0
0 0 0
輸出:
0 0 0
0 1 0
0 0 0
bfs代碼
class Solution {int[][] res;public int[][] updateMatrix(int[][] matrix) {int[][] dir=new int[][]{{-1,0},{1,0},{0,1},{0,-1}};res=new int[matrix.length][matrix[0].length];LinkedList<int[]> queue=new LinkedList<>();for(int i=0;i<matrix.length;i++)for(int j=0;j<matrix[0].length;j++)if(matrix[i][j]==0)//將0元素入隊{res[i][j]=0;matrix[i][j]=-1;queue.add(new int[]{i,j});}while (!queue.isEmpty()){int[] p=queue.removeFirst();int x=p[0],y=p[1];for(int[] d:dir)//4個方向入隊{int nextX=x+d[0],nextY=y+d[1];if(nextX<0||nextY<0||nextX>=matrix.length||nextY>=matrix[0].length||matrix[nextX][nextY]==-1)//不符合的情況剔除continue;res[nextX][nextY]=res[x][y]+1;matrix[nextX][nextY]=-1;queue.add(new int[]{nextX,nextY});}}return res;}
}
動態規劃代碼
class Solution {public int[][] updateMatrix(int[][] matrix) {int n=matrix.length,m=matrix[0].length;int[][] dp=new int[n][m];for(int i=0;i<n;i++)for(int j=0;j<m;j++)dp[i][j]=matrix[i][j]==0?0:100001;for(int i=0;i<n;i++)for(int j=0;j<m;j++)//從左和上推導{ if(i-1>=0)dp[i][j]= Math.min(dp[i][j],dp[i-1][j]+1);if(j-1>=0)dp[i][j]= Math.min(dp[i][j],dp[i][j-1]+1);}for(int i=n-1;i>=0;i--)for(int j=m-1;j>=0;j--)//從右和下推導{ if(i+1<n)dp[i][j]= Math.min(dp[i][j],dp[i+1][j]+1);if(j+1<m)dp[i][j]= Math.min(dp[i][j],dp[i][j+1]+1);} return dp;}
}
)
