글 읽기 - 런타임 에러 질문 남깁니다.

cdt416z 4년 전 0

좌측 벽과 하단의 벽에서부터

다익스트라로 최단 값을 구하는 알고리즘을 썻는데

런타임에러가 걸립니다..

3 3은 잘되는데 5 5부터 런타임에러가 걸리네요

왜 런타임에러가 걸리는건가요??

#include <stdio.h>
#define INF 987654321
#define SWAP(a, b) {int t = a; a = b; b = t;}

int N, M, result = INF;
int map[300][300];
int visit[300][300] = { 0 };
int dijk[300][300] = { 0 };
int heap[100000][3];
int index = 0;
int dweight, xi, xj;
int di[8] = {1, -1, 0, 0, 1, 1, -1, -1};
int dj[8] = {0, 0, 1, -1, 1, -1, 1, -1};

void DFS(int i, int j){
    if(i == N - 1 && j == M - 1){
        return;
    }
    for(int k = 0; k < 4; k++){
        int ni = i + di[k];
        int nj = j + dj[k];
        if(ni < 0 || ni >= N || nj < 0 || nj >= M){
            continue;
        }
        if(map[ni][nj] != -1 || visit[ni][nj] == 1){
            continue;
        }
        visit[ni][nj] = 1;
        DFS(ni, nj);
    }
}

void push(int i, int j, int weight){
    heap[++index][0] = i;
    heap[index][1] = j;
    heap[index][2] = weight;
    for(int i = index; i > 1; i /= 2){
        if(heap[i][2] < heap[i / 2][2]){
            for(int k = 0; k < 3; k++){
                SWAP(heap[i][k], heap[i / 2][k]);
            }
        }
        else{
            break;
        }
    }
}

void pop(){
    xi = heap[1][0];
    xj = heap[1][1];
    dweight = heap[1][2];
    SWAP(heap[1][0], heap[index][0]);
    SWAP(heap[1][1], heap[index][1]);
    SWAP(heap[1][2], heap[index][2]);
    index--;
    for(int i = 1; i * 2 <= index;){
        if(i * 2 + 1 > index){
            if(heap[i][2] > heap[i * 2][2]){
                for(int k = 0; k < 3; k++){
                    SWAP(heap[i][k], heap[i * 2][k]);
                }
            }
            break;
        }
        if(heap[i][2] <= heap[i * 2][2] && heap[i][2] <= heap[i * 2 + 1][2]){
            break;
        }
        else if(heap[i][2] <= heap[i * 2][2]){
            for(int k = 0; k < 3; k++){
                SWAP(heap[i][k], heap[i * 2 + 1][k]);
            }
            i = i * 2 + 1;
        }
        else if(heap[i][2] <= heap[i * 2 + 1][2]){
            for(int k = 0; k < 3; k++){
                SWAP(heap[i][k], heap[i * 2][k]);
            }
            i = i * 2;
        }
        else{
            if(heap[i * 2][2] > heap[i * 2 + 1][2]){
                for(int k = 0; k < 3; k++){
                    SWAP(heap[i][k], heap[i * 2 + 1][k]);
                }
                i = i * 2 + 1;
            }
            else{
                for(int k = 0; k < 3; k++){
                    SWAP(heap[i][k], heap[i * 2][k]);
                }
                i = i * 2;
            }
        }
    }
}

void stra(int i, int j){
    heap[++index][0] = i;
    heap[index][1] = j;
    heap[index][2] = 0;
    while(index){
        pop();
        if(dweight > dijk[xi][xj]){
            continue;
        }
        dijk[xi][xj] = dweight;
        for(int k = 0; k < 8; k++){
            int ni = xi + di[k];
            int nj = xj + dj[k];
            if(ni < 0 || ni >= N || nj < 0 || nj >= M){
                continue;
            }
            if(map[ni][nj] == -1){
                continue;
            }
            push(ni, nj, dijk[xi][xj] + map[ni][nj]);
        }
    }
}

int main(){
    scanf("%d %d", &N, &M);
    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++){
            scanf("%d", &map[i][j]);
            if(map[i][j] == -2){
                map[i][j] = 0;
            }
        }
    }
    visit[0][0] = 1;
    DFS(0, 0);
    if(visit[N - 1][M - 1]){
        printf("-1");
        return 0;
    }
    for(int i = 1; i < N; i++){
        if(map[i][0] != -1){
            for(int j = 0; j < N; j++){
                for(int k = 0; k < M; k++){
                    dijk[j][k] = INF;
                }
            }
            dijk[i][0] = 0;
            stra(i, 0);
            for(int j = 1; j < M; j++){
                if(result > dijk[0][j] + map[i][0]){
                    result = dijk[0][j] + map[i][0];
                }
            }
            for(int j = 1; j < N - 1; j++){
                if(result > dijk[j][M - 1] + map[i][0]){
                    result = dijk[j][M - 1] + map[i][0];
                }
            }
        }
    }
    for(int i = 1; i < M - 1; i++){
        if(map[N - 1][i] != -1){
            for(int j = 0; j < N; j++){
                for(int k = 0; k < M; k++){
                    dijk[j][k] = INF;
                }
            }
            dijk[N - 1][i] = 0;
            stra(N - 1, i);
            for(int j = 1; j < M; j++){
                if(result > dijk[0][j] + map[N - 1][i]){
                    result = dijk[0][j] + map[N - 1][i];
                }
            }
            for(int j = 1; j < N - 1; j++){
                if(result > dijk[j][M - 1] + map[N - 1][i]){
                    result = dijk[j][M - 1] + map[N - 1][i];
                }
            }
        }
    }
    printf("%d", result);
    return 0;
}

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

문제

문제

출처

ICPC

런타임 에러 질문 남깁니다.

cdt416z 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말