글 읽기 - 모든 입력에서 잘 잘동하는데, 그냥 틀렸습니다라고 뜨네요(C++)

dbswns97 4년 전 0

1:1
2:0
3:0
4:2
5:10
6:4
7:40
8:92
9:352
10:724
11:2680
12:14200
13:73712
14:365596

각인풋에 대해 아웃풋은 저렇게 나옵니다. 3%에서 4%으로 넘어갈때 틀렸다고 나오네요.. 어디가 잘못된것이죠?? 도저히 모르겠습니다 ㅠㅠ

도와주세요 고수님들 ㅠㅠ

#include <iostream>
#include <vector>
using namespace std;

bool complete_flag = false;
int gcount = 0;
bool Iscomplete(int depth, int data) {
	if (depth == data-1)
		return true;
	else return false;
}

void FinalProcess(int* arr, int data) {
	/*for (int i = 0; i < data; i++) {
		cout << arr[i] << " ";
	}
	cout << '\n';*/
	gcount++;

}


void check(int*** arr, int depth, int depth2, int data) {
	for (int i = 0; i < data; i++) {
		for (int j = 0; j < data; j++) {
			if (i == depth || j == depth2)
				arr[depth][i][j] = 1;
		}
	}
	int tmp = depth, tmp2 = depth2, tmp3 = depth2;
	while (true) {
		tmp++;
		if (tmp == data)
			break;

		if (--tmp2 != -1)
			arr[depth][tmp][tmp2] = 1;
		if (tmp3 != data)
			arr[depth][tmp][++tmp3] = 1;

	}
	arr[depth][depth][depth2] = 2;

	/*for (int i = 0; i < data; i++) {
		for (int j = 0; j < data; j++) {
			cout << arr[depth][i][j] << " ";
		}
		cout << '\n';
	}
	cout << '\n';*/
}

bool Contains(int* arr, int number, int depth, int depth2, int data, int*** chess) {

	if (chess[depth-1][depth][number] == 0)
		return true;
	else return false;
}

void FindNextTargets(int* arr, int depth, int depth2, int data, int*** chess, int* next_targets, int* num_of_next_targets) {
	int count = 0;
	for (int i = 0; i < data; i++) {
		if (Contains(arr, i, depth, depth2, data, chess))
			next_targets[count++] = i;
	}


	*num_of_next_targets = count;

}
void initialchess(int*** chess, int data) {
	for (int k = 0; k < data; k++)
		for (int i = 0; i < data; i++) {
			for (int j = 0; j < data; j++) {
				chess[k][i][j] = 0;
			}
		}
}


void Backtracking(int* arr, int depth, int depth2, int data, int*** chess) {



	// Check whether this combination is the solution or not/
	if (Iscomplete(depth, data)) {

		FinalProcess(arr, data); // Go ther final process.
		complete_flag = true; //Finish.
	}
	else
	{
		int num_of_next_targets = 0;
		//int *next_targets = new int[data-depth];
		int* next_targets = new int[512];

		if (depth > 0) {
			for (int i = 0; i < data; i++) {
				for (int j = 0; j < data; j++) {
					chess[depth][i][j] = chess[depth - 1][i][j];
				}
			}
		}
		//cout << "arr[depth]" << arr[depth]<<depth << endl;
		check(chess, depth, arr[depth], data);

		

		// Increase the count of depth.
		depth++;
		//depth2++;

		//Udate the list of next targets and the number.
		FindNextTargets(arr, depth, depth2, data, chess, next_targets, &num_of_next_targets);

		//	cout << "depth:"<<depth<<'\n';
		for (int i = 0; i < num_of_next_targets; i++) {
			//	cout << "i:"<<i<<"dd\n";
			arr[depth] = next_targets[i];
			Backtracking(arr, depth, depth2, data, chess);

			//if (complete_flag) return 0;
		}

		delete[] next_targets;
	}
}




int main() {

	int n;

	cin >> n;

		int*** chesspane = new int** [n];
		for (int i = 0; i < n; i++) {
			chesspane[i] = new int* [n];
			for (int j = 0; j < n; j++) {
				chesspane[i][j] = new int[n];
			}
		}
		int* arr = new int[n];

		if (n == 1)
			cout << "1";
		else {
			for (int i = 0; i < n; i++) {
				arr[0] = i;
				initialchess(chesspane, n);
				Backtracking(arr, 0, 0, n, chesspane);
			}
			cout << gcount ;
		}
		delete[] chesspane;
	
	return 0;
}

djm03178 4년 전 1

어딘가 undefined behavior가 있나 봅니다.

https://ideone.com/EL3BPO

dbswns97 4년 전 0

감사합니다. 의심가는곳을 전부 다 수정하니까 인제 시간초과로 틀렸다고 나오네요..

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

문제

문제

출처

ICPC

모든 입력에서 잘 잘동하는데, 그냥 틀렸습니다라고 뜨네요(C++)

dbswns97 4년 전 0

djm03178 4년 전 1

dbswns97 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말