글 읽기 - 왜 틀린 걸까요???

melon940925 4년 전 0

시뮬레이션까지 해봤는데(주석처리로 된 부분이 시뮬레이션입니다.)

제 알고리즘에 어떤 오류가 있어서 답이 틀리는 건지 모르겠어요..

왜 틀렸을까요?

#include <stdio.h> 

int map[110][110];
int dy[] = { -1,1,0,0 };
int dx[] = { 0,0,1,-1 };
typedef struct loc {
    int y;
    int x;
}Loc;

Loc Queue[1000];
int rear;
int visit[110][110];
int front;
int Qcnt;
void push(int y, int x) {
    Queue[rear].y = y;
    Queue[rear].x = x;
    rear++;
    rear %= 1000;
    Qcnt++;
}
void pop() {
    Queue[front].y = -1;
    Queue[front].x = -1;
    front++;
    front %= 1000;
    Qcnt--;

}
int w, h, n;

int dir[100 + 10], len[100 + 10];

int sol;
int det(int y, int x) {
    if (y == 0 || y == h || x == 0 || x == w && y >= 0 && y <= h && x <= w && w >= 0)
        return 1;
    else
        return 0;
}

void BFS() {
    int X, Y, nx, ny;

    int q;

    while (Qcnt > 0) {
        q = Qcnt;
        sol++;


   /*     printf("\n\n");
        for (int j = 0; j <= h; j++) {
            for (int k = 0; k <= w; k++) {
                if (map[j][k] == 1)
                    printf("☆ ");
                else if (visit[j][k] == 0) {
                    printf("○ ");
                }
                else
                    printf("● ");
            }
            printf("\n");
        }*/


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


            X = Queue[front].x; Y = Queue[front].y;
            pop();
            for (int j = 0; j < 4; j++) {
                nx = X + dx[j]; ny = Y + dy[j];
                if (det(ny, nx)) {
                    if (map[ny][nx] == 1) {
                        map[ny][nx] = 0;
                        Qcnt = rear = front = 0;
                     //   printf("sol: %d\n", sol);
                        return;
                    }
                    else if (visit[ny][nx] == 0) {
                        //printf("푸쉬된값 x: %d, y: %d\n", nx, ny);
                        push(ny, nx);
                        visit[ny][nx] = 1;
                    }
                }

            }

        }
        //int k = 1;
        //for (int i = 0; i <= h; i++) {
        //    for (int j = 0; j <= w; j++) {
        //        if (map[i][j] == 1)
        //            k = 0;
        //    }
        //}
        //if (k == 1)
        //    return;
    }


}

int main(void)
{
    int i;
    scanf("%d %d", &w, &h);
    scanf("%d", &n);
    for (i = 0; i <= n; i++)
    {
        scanf("%d %d", &dir[i], &len[i]);
    }

    for (int i = 0; i < n; i++) {
        if (dir[i] == 1) {
            map[0][len[i]] = 1;
        }
        else if (dir[i] == 2) {
            map[h][len[i]] = 1;
        }
        else if (dir[i] == 3) {
            map[len[i]][0] = 1;
        }
        else if (dir[i] == 4) {
            map[len[i]][w] = 1;
        }

    }

    int sy, sx;
    if (dir[n] == 1) {
        sy = 0; sx = len[n];
    }
    else if (dir[n] == 2) {
        sy = h; sx = len[n];
    }
    else if (dir[n] == 3) {
        sy = len[n]; sx = 0;
    }
    else if (dir[n] == 4) {
        sy = len[n]; sx = w;
    }

    while (n >0) {
        push(sy, sx);
        for (int i = 0; i < 110; i++) {
            for (int j = 0; j < 110; j++) {
                visit[i][j] = 0;
            }
        }
        visit[sy][sx] = 1;
        BFS();
        n--;
    }

    printf("%d", sol);
    return 0;
}

//10 10
//3
//4 6
//2 8
//1 4
//1 2
//



//20 20
//4
//4 6
//2 8
//1 9
//4 20
//2 7

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

문제

문제

출처

ICPC

왜 틀린 걸까요???

melon940925 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말