(7576) 토마토

https://www.acmicpc.net/problem/7576

단계별로 풀어보기

27단계(그래프와 순회) 12번째

 

 

 

#include <iostream>
#include <queue>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int m, n, cnt= 0, ans= -1;
  
  cin >> m >> n;
  
  vector v(n, vector<int> (m));
  queue<pair<int,int>> q;
  
  for(int i=0;i<n;i++){
    for(int j=0;j<m;j++){
      cin >> v[i][j];
      
      if(v[i][j]==1)  q.push({i*m+j,0});
      cnt+= v[i][j]>=0;
    }
  }
  
  while(!q.empty()){
    int nowx= q.front().first/m;
    int nowy= q.front().first%m;
    int day= q.front().second;
    cnt--;
    q.pop();
    
    if(!cnt){
      ans= day;
      break;
    }
    
    for(int i=0;i<4;i++){
      int nextx= nowx+"0121"[i]-'1';
      int nexty= nowy+"1012"[i]-'1';
      
      if(nextx<0 || nextx>n-1 || nexty<0 || nexty>m-1)  continue;
      if(v[nextx][nexty]!=0)  continue;
      
      v[nextx][nexty]= 1;
      q.push({nextx*m+nexty,day+1});
    }
  }
  
  cout << ans;
  
  return 0;
}