(7569) 토마토

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

단계별로 풀어보기

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

 

 

 

2차원이 아니라 3차원이라는 점만 빼면 이전 문제와 동일하다.

대신 3개의 변수를 int형 하나로 관리하기는 매우 귀찮기 때문에 좌표용 구조체를 하나 만들었다.

 

 

 

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

struct Cord{
  int x;
  int y;
  int z;
  
  Cord(int x0, int y0, int z0): x(x0), y(y0), z(z0) {}
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int m, n, h, cnt= 0, ans= -1;
  
  cin >> m >> n >> h;
  
  vector v(n, vector (m, vector<int> (h)));
  queue<pair<Cord,int>> q;
  
  for(int k=0;k<h;k++){
    for(int i=0;i<n;i++){
      for(int j=0;j<m;j++){
        cin >> v[i][j][k];
        
        if(v[i][j][k]==1){
          q.push({Cord(i, j, k), 0});
        }
        cnt+= v[i][j][k]>=0;
      }
    }
  }
  
  while(!q.empty()){
    int nowx= q.front().first.x;
    int nowy= q.front().first.y;
    int nowz= q.front().first.z;
    int day= q.front().second;
    cnt--;
    q.pop();
    
    if(!cnt){
      ans= day;
      break;
    }
    
    for(int i=0;i<6;i++){
      int nextx= nowx+"012111"[i]-'1';
      int nexty= nowy+"101211"[i]-'1';
      int nextz= nowz+"111102"[i]-'1';
      
      if(nextx<0 || nextx>n-1 || nexty<0 || nexty>m-1 || nextz<0 || nextz>h-1)  continue;
      if(v[nextx][nexty][nextz]!=0)  continue;
      
      v[nextx][nexty][nextz]= 1;
      q.push({Cord(nextx, nexty, nextz), day+1});
    }
  }
  
  cout << ans;
  
  return 0;
}