글 읽기 - 반례가 있을까요?

jkjan 4년 전 0

가로로만 있는 것, 세로로만 있는 것 해봤는데 무슨 특이 케이스가 있는지 모르겠네요....

각 사각형에 번호를 부여했고

좌표를 입력 받으면 그 범위 내의 사각형을 다 1로 했고

사각형이 1이 아닌 것끼리 그래프를 연결했습니다.

그리고 마지막에 bfs로 다 셌구요.

게시판에 보이는 예외케이스는 다 맞았는데 ..

어느 점에서 구멍이 있는지 도저히 생각이 안 나네요 ..ㅠㅠ

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

using namespace std;

int N, M, K;

void makeGraph(vector<int>* graph, int* squares);
void drawSquares(int* squares);
int bfs(vector<int>* graph, bool* visited, int start);

int main() {
    vector<int> graph[10001];
    int squares[10001] = {0,};
    bool visited[10001] = {false,};
    vector<int> answer;
    cin >> M >> N >> K;
    for (int i = 0; i < K; i++) {
        drawSquares(squares);
    }
    makeGraph(graph, squares);
    for (int i = 1; i <= N*M; i++) {
        if (squares[i] == 0 && !visited[i]) {
            answer.push_back(bfs(graph, visited, i));
        }
    }
    sort(answer.begin(), answer.end());
    cout << answer.size() << endl;
    for (int & ans : answer) {
        cout << ans << ' ';
    }
    return 0;
}

void connect(vector<int>* graph, int a, int b) {
    graph[a].push_back(b);
    graph[b].push_back(a);
}

void makeGraph(vector<int>* graph, int* squares) {
    for (int i = 1; i < N*M; i++) {
        if (squares[i] == 0) {
            if (N != 1 && i % N != 0) {
                if (squares[i+1] == 0)
                    connect(graph, i, i+1);
            }
            if (M != 1 && !((i / N == M-1) && (i % N != 0))) {
                if (squares[i+N] == 0)
                    connect(graph, i, i+N);
            }
        }
    }
}

int posToNum(int x, int y) {
    y = M - y;
    return N * y + x;
}

void drawSquares(int* squares) {
    int x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    x1++; y1++;
    int downLeftSquare = posToNum(x1, y1);
    int upRightSquare = posToNum(x2, y2);
    int height = (y2 - y1);
    int upLeftSquare = downLeftSquare - height*N;
    int downRightSquare = upRightSquare + height*N;

    if (upLeftSquare == upRightSquare) {
        for (int i = upLeftSquare; i <= downLeftSquare; i += N) {
            squares[i] = 1;
        }
    }
    else {
        int nowSquare = upLeftSquare;
        while (nowSquare <= downRightSquare && squares[downRightSquare] == 0) {
            squares[nowSquare] = 1;
            if (nowSquare == upRightSquare) {
                upLeftSquare += N;
                nowSquare = upLeftSquare;
                upRightSquare += N;
            }
            else
                nowSquare++;
        }
    }
}

int bfs(vector<int>* graph, bool* visited, int start) {
    queue<int> willVisit;
    int nowVisit;
    willVisit.push(start);
    visited[start] = true;
    int visitCnt = 1;
    while(!willVisit.empty()) {
        nowVisit = willVisit.front();
        willVisit.pop();
        for (int & itor : graph[nowVisit]) {
            if (!visited[itor]) {
                willVisit.push(itor);
                visited[itor] = true;
                visitCnt++;
            }
        }
    }
    return visitCnt;
}

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

문제

문제

출처

ICPC

반례가 있을까요?

jkjan 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말