542, 01_matrix
====
BFS,
Shortest path
Path existed
====
1. 題目希望將給予的matrix
化成
每個單元離它最近的'0'的距離
2. BFS用的是queue, 因為用了座標
所以用queue< pair<int,int> >來紀錄加入queue的座標
3. 從(0,0)開始做BFS
當queue不為空的時候
-> pop單元
-> 針對pop的動作處理BFS //加入新的單元
//新增step or cost
4. Visited是必須的
產生一個vec<vec<bool>>visited來紀錄已經處理過的單元
以免單元間產生無窮迴圈
->
當沒有visited
且
符合題目條件
則處理
BFS //push
====
class Solution{
public:
vec<vec<int>> updateMatrix( vec<vec<int>>&matrix ){
int m= matrix.size()
int n= matrix[0].size()
queue<pair<int,int>> pq
for i-m
for j-n
if(matrix(i,j) == 0){
//先從'0'開始 因為第一次與零的距離是“0”
//之後逐漸加一
pq.push({i-1, j});
pq.push({i+1, j});
pq.push({i, j-1});
pq.push({i,j-1});
//上下左右加入queue //所有第一層的node
}
int step=0
vec<vec<bool>> visited(m, vec<bool>(n, false) )
while( !pq.empty() ){
step++
int size= pq.size() //紀錄當前的queue size來控制當次需要做多少次
for(i=0; i<size; i++){
auto Front= pq.front()
int x=Front.first
int y=Front.second
pq.pop()
if(x>=0&& y>=0&& x<m&& y<n&& !visited(x,y)&& matrix(x,y)==1){
//開始找‘1’,因為開始要填1到0的距離
visited(x,y)=true
matrix(x,y)=step
//因為拜訪過了 且當前的距離已經填入
pq.push({x-1, j});
pq.push({x+1, j});
pq.push({i, y-1});
pq.push({i,y-1});
//第n次層的上下左右 加入queue
}//if
}//for
}//while
}
};
