글 읽기 - 반례를 다 뒤져봐도 통과합니다(2% 틀림)

rooprete99 1년 전 3

올라와있는 반례를 다 넣어봐도 답이 나오고,

1 1

가장 간과하기 쉽다는 이 반례도 정답으로 1이 나옵니다.

2%에서 틀린 걸 보면 뭔가 간단한 걸 놓친 것 같은데 아무리 봐도 봐도 안 보입니다...조언을 구할 수 있을까요?

#include <iostream>
#include <queue>
#include <cmath>
#include <memory.h>
int g_count[1001][1001][2];
bool g_map[1001][1001];

const int dx[] = { -1, 1, 0, 0 };
const int dy[] = { 0, 0, -1, 1 };
struct Node {
    int x;
    int y;
    int count;
    bool break_wall;
};
void Bfs(Node node, int max_y, int max_x) {
    std::queue<Node> q;
    q.push(node);
    g_count[node.x][node.y][node.break_wall] = node.count;

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

        for (int dir = 0; dir < 4; dir++) {
            Node new_node = cnode;

            new_node.x += dx[dir];
            new_node.y += dy[dir];
            new_node.count++;
            //g_count의 값을 갱신할 수 있는가
            if (new_node.x >= 1 && new_node.x <= max_x
                && new_node.y >= 1 && new_node.y <= max_y
                && (g_count[new_node.x][new_node.y][new_node.break_wall] > new_node.count
                    || g_count[new_node.x][new_node.y][new_node.break_wall] == -1)) {

                if (g_map[new_node.x][new_node.y]) {
                    //갈 수 있는 맵일 경우
                    q.push(new_node);
                    g_count[new_node.x][new_node.y][new_node.break_wall] = new_node.count;
                }
                else if (!new_node.break_wall
                    && (g_count[new_node.x][new_node.y][true] == -1
                    ||g_count[new_node.x][new_node.y][true]>new_node.count)) {
                    //벽이 있을 경우, 아직 벽을 부수지 않았을 경우, 그리고 부수고 넘어갔을 때 기존의 기록을 깰 수 있는 경우
                    new_node.break_wall = true;
                    q.push(new_node);
                    g_count[new_node.x][new_node.y][new_node.break_wall] = new_node.count;
                }
            }
        }

    }
    if (g_count[max_x][max_y][true] == -1
        && g_count[max_x][max_y][false] == -1) {
        std::cout << -1;
    }
    else if (g_count[max_x][max_y][true] == -1) {
        std::cout << g_count[max_x][max_y][false];
    }
    else if (g_count[max_x][max_y][false] == -1) {
        std::cout << g_count[max_x][max_y][true];

    }
    else {
        std::cout << std::min(g_count[max_x][max_y][true], g_count[max_x][max_y][false]);
    }
}


int main() {
    int N, M;
    std::cin >> N >> M;
    std::cin.ignore();
    memset(g_count, -1, 1001 * 1001 * 2);
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            char c = std::cin.get();

            g_map[j][i] = c == '0';
        }
        std::cin.ignore();
    }
    //1,1에서 N,M까지 이동
    Node node{ 1, 1, 1, false };
    Bfs(node, N, M);
}

rooprete99 1년 전 22

통과한 반례들 정리하다보니 다른분들께 도움될 것 같아서... 여기 질문게시판에서 긁어모은 반례들 추가합니다.

2 4
0111
0010

ans: 5

---------

2 4
0111
0110

ans: -1

----------

1 1
0

ans: 1

----------

5 8
01000000
01010000
01010000
01010011
00010010

ans: 20

----------

6 7
0000000
0111111
0100010
0101010
0101010
0001010

ans: 12

---------

8 8
01000100
01010100
01010100
01010100
01010100
01010100
01010100
00010100

ans: 29

----------

3 3
011
111
110

ans: -1

-----------

3 6
010000
010111
000110

ans: 12

-----------

3 3
000
000
000

ans: 5

----------

4 4
0101
0101
0001
1110

ans: 7

5 5
01000
01010
01010
01011
00010

ans: 9

--------

5 5
00000
11101
00001
01111
00010

ans: 15

-------
5 5
01000
01010
01010
01011
00010

ans: 9

------
10 2
01
00
10
00
01
00
10
00
01
00

ans:13

------
5 5
00100
00000
10010
00101
00010

ans:9

------
9 9 
010001000
010101010
010101010
010101010
010101010
010101010
010101010
010101011
000100010

ans:33

--------
6 6
010001
010101
010101
010101
010110
000110

ans:21

---------
5 5
00100
11000
00110
01011
00000

ans:9

------------
8 8
01000100
01010100
01010100
01010100
01010100
01010100
01010100
00010100

답 29
    

5 10
0000011000
1101011010
0000000010
1111111110
1111000000
    
답 14
    
    
5 5
01100
01000
01110
01000
00010
    
답 9
    
    
8 4
0000
0110
1110
0000
0111
0000
1110
0000
    
답 11
    
    
6 4
0000
1110
0110
0000
0111
0000
    
답 9
    
    
8 8
01000100
01010100
01010100
01010100
01010100
01010100
01010100
00010100
    
답 29

rooprete99 1년 전 0

상상도 못한 부분으로 해결됐습니다.

memset에서 size 곱하는 걸 빼먹어서 제대로 초기화가 안 되고 있었네요.

초기화되지 않은 부분까지 쓸 정도로 N과 M이 충분히 큰 반례가 없어서 계속 통과한 것 같습니다;;

반례는 다 통과하는데 제출만 하면 실패하시는 분들 초기화 제대로 되고 있는지 확인해보십쇼...

    memset(g_count, -1, 1001*1001*2);//수정전
    memset(g_count, -1, sizeof(g_count));//수정후

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

문제

문제

출처

ICPC

반례를 다 뒤져봐도 통과합니다(2% 틀림)

rooprete99 1년 전 3

rooprete99 1년 전 22

rooprete99 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말