글 읽기 - 시간초과 ..도와주세용..bfs로했는데 초과뜨네용...

kioio5 7년 전 0

T___T....

어디서 시간이 초과되는걸까요....

중복 push막았다고생각하는데..흠...

#include <stdio.h>
#include <stdlib.h>
#define QUEUE_SIZE 5000000
typedef struct point
{
    int x;
    int y;
    int weight;
} Point;
Point Queue[QUEUE_SIZE];
int front=0;
int rear=0;
int M,N;
int map[1000][1000];
int tomato_total=0;
void push(Point data)
{

    if((rear+1)%QUEUE_SIZE==front)
    {

    }
    else
    {
        rear = (rear+1)%QUEUE_SIZE;
        Queue[rear] = data;
    }
}
Point pop()
{
    Point data;
    if(rear==front)
    {
        data.weight=-1;

    }
    else
    {
        front = (front+1)%QUEUE_SIZE;
        data = Queue[front];
    }
    return data;
}


void input()
{
    int i,j;

    scanf("%d%d",&N,&M);
    for(i=0; i<M; i++)
    {
        for(j=0; j<N; j++)
        {
            scanf("%d",&map[i][j]);
            if(map[i][j]!=-1)tomato_total++;
            if(map[i][j]==1)
            {
                Point data;
                data.x = i;
                data.y = j;
                data.weight = 0;
                push(data);
            }
        }
    }

}
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
int max(int a,int b)
{
    return a>b?a:b;
}
int bfs()
{
    int i;
    int max_day = 0;
    Point p;

    while(1)
    {
        p = pop();
        if(p.weight==-1)//queue is empty
            break;
        tomato_total--;
        max_day = max(p.weight,max_day);
        map[p.x][p.y] = 1;
        for(i=0; i<4; i++)
        {
            Point p2;
            p2.x = p.x+dx[i];
            p2.y = p.y+dy[i];
            p2.weight = p.weight + 1;
            if(Queue[rear].x==p2.x&&Queue[rear].y==p2.y)continue;
            if(p2.x>=M||p2.y>=N||p2.x<0||p2.y<0||map[p2.x][p2.y]!=0)continue;

            push(p2);
           // printf("(%d %d %d)\n",p2.x,p2.y,p2.weight);
        }
    }

    if(tomato_total>0)
        return -1;
    return max_day;
}
void map_print()
{
    int i,j;
    for(i=0; i<M; i++)
    {
        for(j=0; j<N; j++)
            printf("%d ",map[i][j]);
        puts("");
    }

}
int main()
{
    input();
    printf("%d\n",bfs());

    return 0;
}

kioio5 7년 전 0

방문검사를 pop하고 나서가 아닌 push하기 전에 하니 시간초과 문제를 해결할 수 있었습니다.

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

문제

문제

출처

ICPC

시간초과 ..도와주세용..bfs로했는데 초과뜨네용...

kioio5 7년 전 0

kioio5 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말