994, rotting oranges

====

994, rotting oranges

====

BFS,

Shortest path,

Path existed

====

1. 給予一個箱子

'0'代表空

'1'代表好的

'2'代表爛的橘子

每分鐘爛的會向四個方向腐爛

求最大（久）箱子內還有好的

2. 起點是爛的->爛的(2) 座標/pair加入queue

隨後加入找好的(1)

但是要把它變爛(2)才 座標/pair加入queue

3. 多一個int fresh紀錄剩餘的好的

每次BFS加入記得扣掉

多一個int res紀錄第幾輪

return res

//剛開始的BFS還沒開始感染

//所以放在while裡面即可

4. 四個方向化成一個vector

vec<int> for={-1, 0, 1, 0, -1}

//只要1234, 2345 pair就好

====

class Solution{

public:

int orangesRotten( vec<vec<int>>& grid ){

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

  int fresh=0

  queue< pair<int,int>> q

  for i-m

    for j-n

      if grid[i][j] == 2

        q.push(<i-1,j>), q.push(<i+1,j>), q.push(<i,j-1>), q.push(<i,j+1>);

      if grid[i][j] == 1

        fresh++

  vec<vec<bool>> visited(m, vec<bool>(n, flase))

  int res=-1

  while( !q.empty() ){

    int qSize= q.size()

    while(qSize--){

      auto fq= q.front()

      q.pop()

      int x= fq.first

      int y= fq.second

      if(x>=0 && y>=0 && x<m && y<n && !visited[x][y] && grid[x][y]==1){

        visited[x][y]=true

        grid[x][y]=2

        q.push(<x-1,y>), q.push(<x+1,y>), q.push(<x,y-1>), q.push(<x,y+1>);

      }//if

    }//q.size

    res++

  }//q.empty

if(res==-1) return 0

if(fresh>0) return -1 //有橘子永遠不爛 莫急

}

};