글 읽기 - 시간초과.. 더 줄일수있는부분이 있을지.. 알고리즘을 다시짜야할지 문의드립니다.

jameseok 6년 전 0

시간초과.. 더 줄일수있는부분이 있을지.. 알고리즘을 다시짜야할지 문의드립니다.

코드는 우선 입력받은 1을 큐에 넣고 BFS를 진행하는 방식입니다.

​#include <stdio.h>

#include <iostream>

#include <queue>

#include <memory.h>

#include <algorithm>

using namespace std;

int graph[101][101];

struct _my_str

{

    int se;

    int ga;

    int count;

};

queue <_my_str> my_queue;

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

int main()

{

    int M, N, i, j, p, zeroCount = 0, cmpCount = 0;

    _my_str my_str, temp_str;

    scanf("%d %d", &M, &N);

    my_str.count = 0;

    for(i = 0; i < N; i++)

    {

        for(j =0; j < M; j++)

        {

            scanf("%d", &graph[i][j]);

            if(graph[i][j] == 1)

            {

                my_str.se = i;

                my_str.ga = j;

                my_queue.push(my_str);

            }

            else if(graph[i][j] == 0) zeroCount++;

        }

    }

    while(!my_queue.empty())

    {

        my_str = my_queue.front();

        for(p = 0; p < 4; p++)

        {

            temp_str.se = my_str.se + moveTo[p][0];

            temp_str.ga = my_str.ga + moveTo[p][1];

            if(graph[temp_str.se][temp_str.ga] == 0 && temp_str.se >= 0 && temp_str.se < N && temp_str.ga >= 0 && temp_str.ga < M)

            {

                temp_str.count = my_str.count + 1;

                graph[temp_str.se][temp_str.ga] = 1;

                my_queue.push(temp_str);

                cmpCount++;

            }

        }

        my_queue.pop();

    }

    if(cmpCount!=zeroCount) printf("-1");

    else    printf("%d", --temp_str.count);

    return 0;

}

lyzqm 6년 전 0

지금 코드에서는 탐색후 토마토를 익히는(?)방식으로 하신거같은데 그러지 말고

방문여부 배열을 하나 더만들어서 토마토가 익던 안익던 방문했으면 가지 않는 방식으로 하는게 통과될거같은데요?

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

문제

문제

출처

ICPC

시간초과.. 더 줄일수있는부분이 있을지.. 알고리즘을 다시짜야할지 문의드립니다.

jameseok 6년 전 0

lyzqm 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말