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

sctm1219 2년 전 0

질문글에 있는 반례 몇 개랑 문제 예시는 모두 잘 나오는데 채점 중 9%에서 틀립니다..

반례가 있을까요?

#include <iostream>
#include <vector>

std::vector<int> sudoku(81);
bool check;

bool h_check(int n, int r){
    int pos = (n/9)*9;
    for(int i = pos; i<pos+9; i++) if(sudoku[i] == r) return true;
    return false;
}
bool v_check(int n, int r){
    for(int i = n + 9; i<81; i+=9) if(sudoku[i] == r) return true;
    for(int i = n - 9; i>=0; i-=9) if(sudoku[i] == r) return true;
    return false;
}
bool cube_check(int n, int r){
    int a = n % 9, b = n / 9, pos;
    if(a < 3) a = 0;
    else if(a < 6) a = 3;
    else a = 6;
    if(b < 3) b = 0;
    else if(b < 6) b = 27;
    else b = 54;
    pos = a + b;
    for(int i=pos; i<pos+3; i++) if(sudoku[i] == r) return true;
    pos+=9;
    for(int i=pos; i<pos+3; i++) if(sudoku[i] == r) return true;
    pos+=9;
    for(int i=pos; i<pos+3; i++) if(sudoku[i] == r) return true;
    return false;
}

void DFS_SUDOKU(int start){
    if(check) return;
    if(start == 81){
        check = true;
        for(int i = 0; i<81; i++) { std::cout << sudoku[i] << " "; if(i/9 != (i+1)/9) std::cout << "\n";}
        return;
    }
    for(int i=start; i<81; i++){
        if(sudoku[i]) continue;
        for(int j=1; j<10; j++){
            if(h_check(i, j)) continue;
            if(v_check(i, j)) continue;
            if(cube_check(i, j)) continue;
            sudoku[i] = j;
            DFS_SUDOKU(i + 1);
            sudoku[i] = 0;
        }
        if(sudoku[i] == 0) return;
    }
}

int main(){
    check = false;
    for(auto& i : sudoku) std::cin >> i;
    DFS_SUDOKU(0);
    return 0;
}

sctm1219 2년 전 30

스스로 찾아냈지만, 다른 분들 께도 도움 되고자 남깁니다.

제 코드의 경우에는 이 예가 무한루프에 걸리네요.

0 0 0 0 0 0 0 0 9

0 0 0 0 0 0 0 0 8

0 0 0 0 0 0 0 0 7

0 0 0 0 0 0 0 0 6

0 0 0 0 0 0 0 0 5

0 0 0 0 0 0 0 0 4

0 0 0 0 0 0 0 0 3

0 0 0 0 0 0 0 0 2

0 0 0 0 0 0 0 0 1

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

문제

문제

출처

ICPC

반례가 있을까요? ㅜㅜ

sctm1219 2년 전 0

sctm1219 2년 전 30

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말