글 읽기 - 케이스 질문드립니다.

leechhe 8년 전 0

코드는 BFS로 짰고, queue에 들어가는건 점의 좌표와 벽을 부쉈는지 여부입니다.

cost가 모두 1로 같으므로 가장 먼저 발견한 것이 최단거리인 게 확실하므로 (n,m)을 발견하면 바로 종료하도록 짰습니다.

70% 이상 돌았는데 에러나네요 ㅠㅠ 도움 부탁드립니다.

#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
typedef pair<int, int> intPair;
const int dx[4] = { -1,1,0,0};
const int dy[4] = { 0,0,1,-1};
char grid[1005][1005];
int n,m;
bool isValid(int x, int y){
    return 1<=x && x <=n && 1 <= y && y <= m;
}
int main(){
    scanf("%d%d",&n,&m);

    for( int i =1 ; i <= n ; ++i ){
        scanf("%s", grid[i]+1);
    }
    if( n == 1 && m == 1 ){
        printf("1");
        return 0;
    }
    queue<pair<intPair,bool>> q;
    q.push(make_pair(intPair(1,1),0));
    int ret = 1;
    bool reached = false;
    bool visited[1001][1001] = { false };
    visited[1][1] = true;
    while (!q.empty()) {
        int len = (int)q.size();
        for( int i = 0; i < len ; ++i ){
            int x = q.front().first.first, y = q.front().first.second;
            bool crashed = q.front().second;
            q.pop();
            
            for( int k = 0 ; k < 4 ; ++k ){
                int cx = x+dx[k], cy = y+dy[k];
                if( cx == n && cy == m ){
                    reached = true;
                    break;
                }
                if( !isValid(cx, cy) ) continue;
                if( visited[cx][cy] ) continue;
                visited[cx][cy] = true;
                bool isWall = grid[cx][cy] =='1';
                if( crashed && isWall ) continue;
//                printf("turn %d : (%d,%d)%d\n", ret, cx,cy,cst||isWall);
                q.push(make_pair(intPair(cx,cy),crashed||isWall));
            }
            if (reached)
                break;
        }
        ++ret;
        if( reached ) break;
    }
    if(!reached) ret = -1;
    printf("%d", ret);
    return 0;
}

portableangel 8년 전 6

아마 그런 케이스가 있을 것 같진 않지만, n,m이 1일 때 답이 1이 맞나요?

5 8
01000000
01010000
01010000
01010011
00010010

이 케이스에서, 1열,3열의 벽은 건드리지 않고 멀리 돌아 (n,m) 근처까지 와야 벽을 부수고 들어갈 수가 있습니다.

현재 코드는 마지막 (n,m)을 둘러싼 벽 앞까지 최단경로로 벽을 부수면서 온 뒤 벽을 부수지 못해 -1을 출력하고 있네요.

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

문제

문제

출처

ICPC

케이스 질문드립니다.

leechhe 8년 전 0

portableangel 8년 전 6

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말