글 읽기 - 제가 못찾은 반례가 있을까요?

guddydcjswo1 5년 전 0

다른 예제 입력해도 맞는데 자꾸 틀렸다고 나오네요...

#include<iostream>
#include<vector>

using namespace std;

int arr[9][9];
vector<vector<int>> possible(9);

bool check(int r, int c) {
	for (int i = 0; i < 9; i++) {
		if (i == r)
			continue;
		int r_s = r / 3 * 3;
		int c_s = c / 3 * 3;
		if (arr[i][c] == arr[r][c])
			return false;
		for(int i=r_s;i<r_s+3;i++)
			for (int j = c_s; j < c_s + 3; j++) {
				if (i == r && j == c)
					continue;
				if (arr[i][j] == arr[r][c])
					return false;
			}
	}
	return true;
}

bool go(int index) {
	if (index == 9) {
		return true;
	}
	for (int itr = 0; itr < 9; itr++) {
		if (arr[index][itr] != 0)
			continue;
		for (int i = 0; i < possible[index].size(); i++) {
			int tmp = possible[index].back();
			possible[index].pop_back();
			arr[index][itr] = tmp;
			if (check(index, itr)) {
				if (possible[index].size() == 0) {
					if (go(index + 1))
						return true;
				}
				else {
					if (go(index))
						return true;
				}
			}
			possible[index].insert(possible[index].begin(), tmp);
		}
	}
	return false;
}

int main() {
	for (int i = 0; i < 9; i++) {
		vector<int> tmp(10,0);
		for (int j = 0; j < 9; j++) {
			cin >> arr[i][j];
			tmp[arr[i][j]] = 1;
		}
		for (int j = 1; j < 10; j++)
			if (tmp[j] == 0)
				possible[i].push_back(j);
	}

	go(0);

	for (int i = 0; i < 9; i++) {
		for (int j = 0; j < 9; j++) {
			cout << arr[i][j] << ' ';
		}
		cout << '\n';
	}
	return 0;
}

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

문제

문제

출처

ICPC

제가 못찾은 반례가 있을까요?

guddydcjswo1 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말