542, 01_matrix

====

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

}

};