글 읽기 - 반례가 있을까요..? 제 눈에는 안 보입니다ㅠㅠ

jnary 1년 전 0

예제는 다 맞게 출력되는데, 틀렸습니다가 나오는 원인을 찾지 못하겠습니다 ㅠㅠ

주실 답변에 미리 감사드립니다:)

//BOJ_4963 섬의 개수 [실버 2]
//https://www.acmicpc.net/problem/4963

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

bool map[51][51];
bool check[51][51];
void test_case(int w, int h) {
    memset(check, 0, sizeof(check));
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            cin >> map[i][j];
        }
    }

    queue<pair<int, int>> q;
    int cnt = 0;
    while(1) {
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                if (map[i][j] && !check[i][j]) {
                    q.push({i, j});
                    check[i][j] = 1;
                    break;
                }
            }
            if (!q.empty()) break;
        }

        if (q.empty()) break;
        cnt++;

        while(!q.empty()) {
            int x = q.front().first;
            int y = q.front().second;
            q.pop();

            if (y > 0 && map[x][y-1] && !check[x][y-1]) {
                q.push({x, y-1});
                check[x][y-1] = 1;
            }
            if (map[x][y+1] && !check[x][y+1]) {
                q.push({x, y+1});
                check[x][y+1] = 1;
            }
            if (x > 0 && map[x-1][y] && !check[x-1][y]) {
                q.push({x-1, y});
                check[x-1][y] = 1;
            }
            if (map[x+1][y] && !check[x+1][y]) {
                q.push({x+1, y});
                check[x+1][y] = 1;
            }
            if (x > 0 && y > 0 && map[x-1][y-1] && !check[x-1][y-1]) {
                q.push({x-1, y-1});
                check[x-1][y-1] = 1;
            }
            if (y > 0 && map[x+1][y-1] && !check[x+1][y-1]) {
                q.push({x+1, y-1});
                check[x+1][y-1] = 1;
            }
            if (x > 0 && map[x-1][y+1] && !check[x-1][y+1]) {
                q.push({x-1, y+1});
                check[x-1][y+1] = 1;
            }
            if (map[x+1][y+1] && !check[x+1][y+1]) {
                q.push({x+1, y+1});
                check[x+1][y+1] = 1;
            }
        }

    }
    cout << cnt << endl;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);

    while(1) {
        int w, h; cin >> w >> h;
        if (!w && !h) break;
        test_case(w, h);
    }
}

park98sj 1년 전 1

x+1이나 y+1일때 배열 범위를 확인해야 할 것 같네요

그리고 8방 탐색에 대해 한 번 찾아보시면 좋을 것 같아요.

ex) 아래의 dx, dy를 사용해서 문제 푸는 법

int dx[]={1, -1, 0, 0, 1, 1, -1, -1};

int dy[]={0, 0, 1, -1, 1, -1, 1, -1};

jnary 1년 전 0

감사합니다!! 덕분에 해결했습니다 !!

8방 탐색에 대해서도 알려주셔서 감사합니다 !!

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

문제

문제

출처

ICPC

반례가 있을까요..? 제 눈에는 안 보입니다ㅠㅠ

jnary 1년 전 0

park98sj 1년 전 1

jnary 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말