글 읽기 - 시간초과,,, 왜나는지 못찾겠어요ㅜㅜ

sgh280 5년 전 0

아무리 찾아봐도 못찾겠습니다 ㅜㅜ

#include <stdio.h>

#include <iostream>

#include <deque>

using namespace std;

int n,m,notom=0,day=0;

deque<pair<int, int>> q;

int dir[4][2]={{-1,0},{1,0},{0,1},{0,-1}};

int tomato[1000][1000];

int isall(){

    int cnt=0;

    for(int i=0;i<m;i++){

        for(int j=0;j<n;j++)

        {

            if(tomato[i][j]==1){

                cnt++;

            }

        }

    }

    if(n*m-notom!=cnt){

        return 0;

    }

    else

        return 1;

}

int bfs(){

    if(q.empty()){

        return -1;

    }

    while (!q.empty()) {

        int cur=q.size();

        for(int j=0;j<cur;j++) {

            int x= q.front().second;

            int y=q.front().first;

            q.pop_front();

            for(int i=0;i<4;i++)

            {

                int n_y=y+dir[i][0];

                int n_x=x+dir[i][1];

                if(n_x>=0&&n_x<n&&n_y>=0&&n_y<m&&tomato[n_y][n_x]==0){

                    tomato[n_y][n_x]=1;

                    q.push_back({n_y,n_x});

                }

            }

            if(isall()==1&&q.empty()==1){

                return day;

            }

            else if(isall()!=1&&q.empty()==1)

                return -1;

        }

        day++;

    }

    return 0;

}

int main(){

    cin >> n>>m;

    for(int i=0;i<m;i++){

        for(int j=0;j<n;j++)

        {

            cin >> tomato[i][j];

            if(tomato[i][j]==1){

                q.push_back({i,j});

            }

            else if(tomato[i][j]==-1){

                notom++;

            }

        }

    }

    if(q.size()==n*m-notom){

        cout<<0;

    }

    else

        cout << bfs();

}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

시간초과,,, 왜나는지 못찾겠어요ㅜㅜ

sgh280 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말