글 읽기 - 어떤게 틀렸을까요 고수형님들

nexus94 4년 전 1

que에 좌표와 벽 뚫기 가능여부, 거리를 저장하고

거리를 하나씩 늘려주며 목적지에 도달하면 해당 거리를 출력해주는 코드입니다.

BFS이니 가장 빠른 답이 최소일거라고 생각했고, 모든 경우의 수를 방문하기 때문에 예외가 없을거라고 생각했는데 아닌가봐요..

무엇이 문제일까요? 도와주세요 !!

#include <iostream>
#include <queue>
using namespace std;

int N, M;
int arr[1001][1001];
bool visited[1001][1001];
int da[4] = {1, -1, 0, 0};
int db[4] = {0, 0, -1, 1};
// <<a, b>, <item, distance>>
queue< pair< pair<int, int>, pair<bool, int> > > que;

void push_que( int a, int b, bool item, int distance ){
    que.push(make_pair(make_pair(a, b), make_pair(item, distance)));
}

int main()
{
    int result = -1;
    
    cin >> N >> M;
    for( int i = 0; i < N; i++ ){
        for( int j = 0; j < M; j++ ){
            scanf("%1d", &arr[i][j]);
            visited[i][j] = false;
        }
    }
    
    
    push_que(0, 0, 1, 1);
    visited[0][0] = 1;
    while( !que.empty() ){
        int front_a = que.front().first.first;
        int front_b = que.front().first.second;
        bool front_item = que.front().second.first;
        int front_distance = que.front().second.second;
        if( front_a == N - 1 && front_b == M - 1 ){
            result = front_distance;
            break;
        }
        que.pop();
        
        for( int i = 0; i < 4; i++ ){
            int tmpa = front_a + da[i];
            int tmpb = front_b + db[i];
            
            if( tmpa < 0 || tmpa >= N || tmpb < 0 || tmpb >= M )
                continue;
            if( arr[tmpa][tmpb] == 0 && !visited[tmpa][tmpb] ){
                visited[tmpa][tmpb] = 1;
                push_que(tmpa, tmpb, front_item, front_distance + 1);
            } else if( arr[tmpa][tmpb] == 1 && !visited[tmpa][tmpb] && front_item ){
                visited[tmpa][tmpb] = 1;
                push_que(tmpa, tmpb, 0, front_distance + 1);
            }
        }
    }
    
    cout << result << endl; 
     
    return 0;
    
    
}

surung9898 4년 전 3

반례는 다음과 같습니다.

/*
6 5
00000
11110
00000
01111
01111
00010

answer: 18
output: -1

nexus94 4년 전 1

정말 감사합니다 ...

덕분에 문제를 풀게되었습니다 ㅜㅜ

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

문제

문제

출처

ICPC

어떤게 틀렸을까요 고수형님들

nexus94 4년 전 1

surung9898 4년 전 3

nexus94 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말