글 읽기 - 테스트 케이스 모두 맞는데 어디서 틀린지 모르겠습니다.

ih0070 4년 전 0

처음에 시간초가 걸려서 밤인 부분은 미리 하루 더 지난것을 체크하는것으로 바꿨는데 그러면 틀린다고 뜨네요

#include <cstdio>
#include <queue>

using namespace std;
int n, m, k, result = 0x79999999;
char map[1001][1001] = { 0, };
bool visited[1001][1001][11] = { 0, };
int dx[] = { 1,-1,0,0 };
int dy[] = { 0,0,1,-1 };

struct Node {
    int x, y, dist, crash;
};

void bfs() {
    queue<Node> q;
    q.push({ 0,0,1,k });

    for (int i = k; k >= 0; k--) {
        visited[0][0][i] = true;
    }

    while (!q.empty()) {
        Node temp = q.front();
        q.pop();

        int _x = 0, _y = 0, _dist = 0, _crash = 0;

        //탈출 조건 
        if (temp.x == n - 1 && temp.y == m - 1) {
            result = result > temp.dist ? temp.dist : result;
            break;
        }

        //4방향 
        for (int i = 0; i < 4; i++) {
            int x1 = temp.x + dx[i];
            int y1 = temp.y + dy[i];

            if (visited[x1][y1][temp.crash] == true)
                continue;

            if (x1 < 0 || x1 >= n || y1 < 0 || y1 >= m)
                continue;

            //낮
            if (temp.dist % 2 == 1) {
                if (map[x1][y1] == '1' && temp.crash > 0) {   // 벽 해머 있으면 뚫기 
                    visited[x1][y1][temp.crash - 1] = true;
                    q.push({ x1,y1,temp.dist + 1, temp.crash - 1 });
                  //  printf("temp (%d,%d) --> (%d,%d) ,dist= %d, crash =%d \n", temp.x, temp.y, x1, y1, temp.dist + 1, temp.crash - 1);
                }
                else if (map[x1][y1] == '0') { //길 
                    visited[x1][y1][temp.crash] = true;
                    q.push({ x1,y1,temp.dist + 1, temp.crash });
                  //  printf("temp (%d,%d) --> (%d,%d) ,dist= %d, crash =%d \n", temp.x, temp.y, x1, y1, temp.dist + 1, temp.crash );
                }
            }
            //밤
            else {
                if (map[x1][y1] == '1' && temp.crash >0) {  //벽 제자리 
                    visited[temp.x][temp.y][temp.crash] = true;
                    _x = x1;
                    _y = y1;
                    _dist = temp.dist + 2;
                    _crash = temp.crash - 1;
                }
                else if (map[x1][y1] == '0') {  //길 
                    visited[x1][y1][temp.crash] = true;
                    q.push({ x1,y1,temp.dist + 1, temp.crash });
                   // printf("temp (%d,%d) --> (%d,%d) ,dist= %d, crash =%d \n", temp.x, temp.y, x1, y1, temp.dist + 1, temp.crash );
                }
            }
            
            if (_dist != 0)
                q.push({ _x,_y,_dist,_crash });
        }

    }
    if (result == 0x79999999) result = -1;
}

int main() {
    //freopen("input.txt", "r", stdin);
    scanf("%d %d %d", &n, &m, &k);

    for (int i = 0; i < n; i++) {
        scanf("%s", map[i]);
    }

    bfs();
    printf("%d\n", result);

    return 0;
}

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

문제

문제

출처

ICPC

테스트 케이스 모두 맞는데 어디서 틀린지 모르겠습니다.

ih0070 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말