글 읽기 - 반례를 도저히못찾겠습니다..

gshs340207 6년 전 0

하루종일 붙잡고있는데 반례를 도저히못찾겠습니다;;

누가좀 도와주세요ㅜㅜ

#include <stdio.h>
#include <queue>
using namespace std;

int wx[4]={1,-1,0,0};
int wy[4]={0,0,1,-1};
bool visit[1100][1100];
int box[1100][1100];
int day[1100][1100];
int N, M, grown, all;
queue < pair<int, int> > Q;

void BFS()
{
    grown=0;
    all=N*M;
    for (int i=1; i<=M; i++)
    {
        for (int j=1; j<=N; j++)
        {
            if (box[i][j]==1)
            {
                day[i][j]=0;
                Q.push(make_pair(i, j));
            }
            if (box[i][j]==-1) all--;
        }
    }
    while (!Q.empty())
    {
        int topx, topy;
        topx = Q.front().first;
        topy = Q.front().second;
        Q.pop();
        if (visit[topx][topy]==0)
        {
            visit[topx][topy]=true;
            grown++;
            if (grown==all)
            {
                printf ("%d\n", day[topx][topy]);
                return;
            }
            for (int i=0; i<4; i++)
            {
                int expx = topx + wx[i];
                int expy = topy + wy[i];
                if (expx<1 || expy<1 || expx>M || expy>N || box[expx][expy]==-1 || box[expx][expy]==1) continue;
                if (visit[expx][expy]==0)
                {
                    day[expx][expy]=day[topx][topy]+1;
                    Q.push(make_pair(expx, expy));
                }
            }
        }
    }
    printf ("-1");
}

int main()
{
    scanf ("%d %d", &N, &M);
    for (int i=1; i<=M; i++)
    {
        for (int j=1; j<=N; j++)
        {
            scanf ("%d", &box[i][j]);
        }
    }
    BFS();
}

sgchoi5 6년 전 0

저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력 => 이 조건에 대한 처리가 없어보입니다.

그리고, 많이 쓰이는 방식으로 코딩하시는 걸 추천드립니다..

행은 N 과 Y 과 I 로 열은 M 과 X 와 J 로 보통 처리하는데,

행을 증가하면서 열을 검사하는 방식으로 하시길 추천 드려요..

for (int i=1; i<=N; i++)
{
for (int j=1; j<=M; j++)
{
day[i][j]=0;
}

}

이런 방식이 캐쉬 히트에 도움이 된다 이런 얘기를 본적이 있기는 한데 얼마나 도움이 될지는 모르겠고,

우선은 정석적인 코딩을 하시길 추천드립니다..

djm03178 5년 전 1

뒷북이지만 모든 토마토가 익어있는 경우에 대한 처리는 되어 있는 코드입니다. 문제가 되는 것은 i일째에 방문될 예정인 칸이, 인접한 다른 i일째에 방문된 칸에 의해 i+1일에 방문되는 것으로 갱신되는 문제가 발생한다는 점입니다.

4 2

1 0 0 1

-1 -1 -1 -1

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

문제

문제

출처

ICPC

반례를 도저히못찾겠습니다..

gshs340207 6년 전 0

sgchoi5 6년 전 0

djm03178 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말