글 읽기 - 로직체크 부탁드립니다 ㅠㅠ

ldg1291 5년 전 0

문제에서 제공하는 테스트케이스는 모두 성공입니다 ㅜㅜ

어느부분이 시간초과가 나는지 전혀 모르겠네요 시도 경우를 상당히 줄였다고 생각이 드는데요..

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

using namespace std;

vector<vector<int>> lines;

set<pair<int, int>> vacant;

set<int> oddindex;

int N, M, H;

bool check();

int answer = 100;

void dfs(set<pair<int,int>>::iterator start, int line) {
    
    if (M == 0) {
        answer = 0;
        return;
    }
    
    if (line > 3) return;
    
    if (line >= 0 && line <= 3 && check()) {
        answer = min(answer, line);
        return;
    }
    
    for (auto i = start; i != vacant.end(); i++) {
        pair<int, int> now = *i;
        if (now.first - 1 >= 0 && lines[now.first-1][now.second] == 100) {
            lines[now.first - 1][now.second] = now.first;
            lines[now.first][now.second] = now.first - 1;
            dfs(next(i,1), line + 1);
            lines[now.first - 1][now.second] = 100;
            lines[now.first][now.second] = 100;
        }
        if (now.first + 1 < N && lines[now.first + 1][now.second] == 100) {
            lines[now.first + 1][now.second] = now.first;
            lines[now.first][now.second] = now.first + 1;
            dfs(next(i, 1), line + 1);
            lines[now.first + 1][now.second] = 100;
            lines[now.first][now.second] = 100;
        }
    }
}

int main()
{
    scanf("%d %d %d", &N, &M, &H);
    
    vector<int> tmp;
    tmp.assign(H, 100);
    lines.assign(N, tmp);
    
    for(int i=0;i<M; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        lines[b - 1][a - 1] = b;
        lines[b][a - 1] = b - 1;
        if(oddindex.find(b) == oddindex.end()) {
            oddindex.insert(b);
        } else oddindex.erase(b);
    }
    
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < H; j++) {
            if (lines[i][j] == 100) vacant.insert({ i,j });
        }
    }
    
    if(oddindex.size() <=3) {
        dfs(vacant.begin(), 0);
    }
    
    answer = answer == 100 ? -1 : answer;
    
    cout << answer << endl;
}

bool check() {
    for (int i = 0; i < lines.size(); i++) {
        int num = i;
        for (int j = 0; j < H; j++) {
            if (lines[num][j] != 100) {
                num = lines[num][j];
            }
        }
        if (num != i) return false;
    }
    return true;
}

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

문제

문제

출처

ICPC

로직체크 부탁드립니다 ㅠㅠ

ldg1291 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말