1162, As far from land as possible

====

1162, As far from land as possible

====

BFS,

Shortest path

Path existed

====

1. 目標是water, '0'

能有與

起點land, '1'能有的最長距離

2. 

定義一個queue<pair<int,int>>存放座標

BFS第一輪找的是起點->從'1'開始上下左右加第一輪BFS

3. 當queue不為空

front && pop座標

如果符合條件 //!visited && 是目標'0'

=>

visited true/ update cost/ 加入上下左右BFS

4. 當最遠的座標找到 會結束

=>

最遠的座標 在上一輪會將上下左右加入queue

=>

新的一輪 for step++

=>

都不符合條件 pop

一直都沒有符合條件的座標 所以都沒有加入queue

=>

while queue空了 跳出

=>

這次的step無作用

step-1才是預期

====

class Solution{

public:

int maxDistance( vec<vec<int>>& matrix ){

  int m= matrix.size(), n= matrix[0].size()

  vec<vec<bool>> visited= (m, vec<bool>(n, false))

  queue<pair<int,int>> pq

  for i-m

    for j-n

      if matrix(i,j) == 1

        pq.push(i-1,j)

        pq.push(i+1,j)

        pq.push(i,j-1)

        pq.push(i,j+1)

  int step=0

  while(!pq.empty()){

    step++

    int size=pq.size()

    for t-size{

    int x= pq.front().first

    int y= pq.front().second

    pq.pop()

    if( x>=0 && y>=0 && x<m && y<n && matrix(x,y)==0 && !visited(x,y) ){

      visited(x,y) = true

      pq.push(x-1,y)

      pq.push(x+1,y)

      pq.push(x,y-1)

      pq.push(x,y+1)

    }//if

    }//for

  }//while

  return step==1? -1: step-1

}

};