生活随笔
收集整理的這篇文章主要介紹了
LeetCode 542 01 矩阵
小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.
題目描述
給定一個由
0 和
1 組成的矩陣，找出每個元素到最近的
0 的距離。
兩個相鄰元素間的距離為
1 。
題解
廣度優(yōu)先搜索
代碼
class Solution
{
public
:vector
<vector
<int>> updateMatrix(vector
<vector
<int>>& matrix
) {int m
=matrix
.size();if (!m
) return {};int n
=matrix
[0].size();vector
<vector
<int>> dp(m
,vector
<int>(n
,-1));queue
<pair
<int,int>> que
;for (int i
=0;i
<m
;i
++){for (int j
=0;j
<n
;j
++){if (!matrix
[i
][j
]) {dp
[i
][j
]=0;que
.push({i
,j
});}}}int d
[4][2]={0,1,1,0,0,-1,-1,0};while (!que
.empty()){int cnt
=que
.size();while (cnt
--){pair
<int,int> tmp
=que
.front();que
.pop();for (int k
=0;k
<4;k
++){int x
=tmp
.first
;int y
=tmp
.second
;int xx
=x
+d
[k
][0];int yy
=y
+d
[k
][1];if (xx
<0||yy
<0||xx
>=m
||yy
>=n
||dp
[xx
][yy
]!=-1) continue;dp
[xx
][yy
]=dp
[x
][y
]+1;que
.push({xx
,yy
});}}}return dp
;}
};
總結
以上是生活随笔為你收集整理的LeetCode 542 01 矩阵的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。
