fork download
copy 
  1. //2234
  2. #include <iostream>
  3. #include <vector>
  4. #include <queue>
  5. #include <utility>
  6. #define MAX 1001
  7. using namespace std;
  8. int matrix[MAX][MAX], visited[MAX][MAX], cX[4]={0,1,0,-1}, cY[4]={1,0,-1,0};
  9. int ans=0;
  10.  
  11. void bfs(int maxX, int maxY){
  12.     queue<pair<int,int>> q;
  13.     for(int y=0;y<maxY;y++){
  14.             for(int x=0;x<maxX;x++)
  15.                 if(matrix[y][x]==1&&!visited[y][x]) q.push(make_pair(x,y));
  16.     }
  17.  
  18.     while(!q.empty()){ // 종료조건 추가해야됨 que에 push할게 없는데 matrix[x][y]==0인 케이스
  19.         //pop하는 과정
  20.         while(!q.empty()){
  21.             int x=q.front().first, y=q.front().second;
  22.             visited[y][x]=1; q.pop();
  23.             for(int i=0;i<4;i++){
  24.                 if(matrix[y+cY[i]][x+cX[i]]!=-1) matrix[y+cY[i]][x+cX[i]]=1;
  25.             }
  26.         } ans++;
  27.  
  28.         //push하는 과정
  29.         for(int y=0;y<maxY;y++){
  30.             for(int x=0;x<maxX;x++){
  31.                 if(matrix[y][x]==1&&!visited[y][x]) q.push(make_pair(x,y));
  32.             }            
  33.         }
  34.     } 
  35.  
  36.     for(int y=0;y<maxY;y++){
  37.         for(int x=0;x<maxX;x++){
  38.             if(matrix[y][x]==0) {cout<<"-1"; return;}
  39.         }
  40.     } cout<<ans-1;
  41. }
  42.  
  43. int main(){
  44.     int M,N; cin>>M>>N;
  45.     for(int i=0;i<N;i++){
  46.         for(int j=0;j<M;j++)
  47.             cin>>matrix[i][j];
  48.     } bfs(M,N);
  49. }
  50. /*
  51. * bfs를 이용
  52.   1. (matrix[x][y]==1, visited[x][y]=0)인값들을 쭉훑어서 queue에 push
  53.   2. 큐가 빌때까지 pop하면서 상하좌우값이 0이면 1로 바꿀예정 -1이면 그냥 넘어감 
  54.   3. 모두 pop했을때 최소날 하루++ / (pop할때 visited[x][y]=1 해줄것)
  55.   
  56.   1,2,3을 계속 반복한후 matrix가 모두 1이면 최소날 출력
  57.   근데 저장될때부터 모든 토마토가 익어있는 상탠지 모두 익지 못하는 상탠지 판단하는게 고민이네
  58.   
  59. */
Success #stdin #stdout 0.01s 5576KB
comments (?)
stdin
copy 
5 5
-1 1 0 0 0
0 -1 -1 -1 0
0 -1 -1 -1 0
0 -1 -1 -1 0
0 0 0 0 0
stdout
copy 
14
https://ideone.com/OpRmd3
language:
C++ (gcc 8.3)
created:
2 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!