글 읽기 - [벽뚫기 질문] 틀렸습니다가 나옵니다.

phk707kr 7년 전 0

물론 틀렸으니까 틀렸다고 나왔겠지만...

질문에 있는 돌발 샘플도 넣어보고, 문제에 제시된 샘플도 통과하는데 어디서 틀렸는지 모르겠습니다.

BFS를 사용했고,

1. 펀치를 썼다면 큐에 펀치를 쓴 정보를 같이 담아서 보냈습니다.

//
//  bfs_miro.c
//  20160830
//
//  Created by 박현규 on 2016. 8. 30..
//  Copyright © 2016년 박현규. All rights reserved.
//


#include <stdio.h>
#include <stdbool.h>

#if 1

#define Q_SIZE 20000

//  bfs, 2206 벽 부수고 이동하기

struct node{
    int y;
    int x;
    bool punch;
};

int map[1001][1001];
int visit[1001][1001];
struct node q[Q_SIZE];
int N, M;
int dir[4][2] = {
    {-1, 0}, {1, 0}, {0, -1}, {0, 1}
};

void printMap(int y, int x){
    int i, j;
    for(i=0; i<y; i++){
        for(j=0; j<x; j++)printf("%d", map[i][j]);
        printf("\n");
    }
    
    printf("\n");
}

void printVisit(int y, int x){
    int i, j;
    for(i=0; i<y; i++){
        for(j=0; j<x; j++)printf("%d", visit[i][j]);
        printf("\n");
    }
    
    printf("\n");
}

int bfs(int y, int x){
    int rear, front;
    int nowy, nowx, i;
    int diry, dirx;
    
    rear = 0;
    front = 0;
    
    q[front].y = y;
    q[front].x = x;
    visit[y][x] = 1;
    
    map[y][x] = 9;
    front++;
    
    while(rear <= front){
        nowy = q[rear].y;
        nowx = q[rear].x;
        
        for(i=0; i<4; i++){
            
            diry = nowy + dir[i][0];
            dirx = nowx + dir[i][1];
            
            /* 갈 수 있는 범위 내에서 map이 1이거나 0인 경우 일단 들어간다. */
            if(diry >= 0 && diry < N && dirx >= 0 && dirx < M && (map[diry][dirx] == 1 || map[diry][dirx] == 0)){
                /* 가려는 위치의 이동했던 거리 < 지금 위치까지 이동한 길이 */
                if(map[diry][dirx] == 1 && visit[diry][dirx] < visit[nowy][nowx]){
                    /* 벽이 있는데 펀치가 있는 경우 */
                    if(q[rear].punch == true){
                        /*
                         1. 현재 펀치는 당연히 없어지는게 아니다?
                         2. 다음 펀치도 없는 걸로
                         */
                        q[front].punch = false;
                        q[front].y = diry;
                        q[front].x = dirx;
                        visit[diry][dirx] = visit[nowy][nowx] + 1;
                        map[diry][dirx] = 9;
                        front++;
                    }
                }
                else if(map[diry][dirx] == 0 && visit[diry][dirx] < visit[nowy][nowx]){
                    /* 
                     1. 벽이 없이 왔는데
                     2. 펀치가 있는 상태로 온 경우
                     3. 펀치가 없는 상태로 온 경우 <- 여기가 중요
                     */
                    
                    if(q[rear].punch == true){
                        q[front].y = diry;
                        q[front].x = dirx;
                        visit[diry][dirx] = visit[nowy][nowx] + 1;
                        map[diry][dirx] = 9;
                        front++;
                    }
                    else if(q[rear].punch == false){
                        q[front].punch = q[rear].punch;
                        q[front].y = diry;
                        q[front].x = dirx;
                        visit[diry][dirx] = visit[nowy][nowx] + 1;
                        map[diry][dirx] = 9;
                        front++;
                    }
                    
                }
            }
        }
        
        //printVisit(N, M);
        
        rear++;
    }
    
    return 0;
}

int main (void){
    int i, j;
    char input[1001];
    
    for(i=0; i<1001; i++){
        for(j=0; j<1001; j++) map[i][j] = 3;
    }
    
    scanf("%d %d", &N, &M);
    for(i=0; i<N; i++){
        scanf("%s", input);
        for(j=0; j<M; j++){
            map[i][j] = input[j] - '0';
        }
    }
    
    for(i=0; i<Q_SIZE; i++) q[i].punch = true;
    
    //printMap(N+1, M+1);
    
    bfs(0, 0);
    
    if(visit[N-1][M-1] != 0) printf("%d\n", visit[N-1][M-1]);
    else printf("-1\n");
    
    return 0;
}
#endif

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

문제

문제

출처

ICPC

[벽뚫기 질문] 틀렸습니다가 나옵니다.

phk707kr 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말