글 읽기 - 62%에서 틀렸습니다가 뜹니다

jsoomin0103 3년 전 0

dfs로 가로선을 0개부터 3개까지 추가해가며 계산중입니다

반례나 제 소스의 틀린점 말씀해주시면 감사하겠습니다ㅠㅠ

#include <iostream>
#include <algorithm>
#pragma warning(disable:4996)

using namespace std;

int N, M, H;//세로선,가로선,높이
int arr[35][35];

int result = -1;
//bool check = false;//찾으면 true로 갱신

void solve(int x, int y, int cnt, int num) {
	//if (check) {
	//	return;
	//}//최소 개수 찾은 경우
	if (cnt > num) {
		return;
	}

	if (cnt == num) {
		int temp_x=1, temp_y;
		for (int i = 1; i <= N; i++) {
			temp_y = i;//마지막에 어디로 도달하는지 저장
			temp_x = 1;
			while (1) {
				if (temp_x > H) {
					break;
				}//탐색 완료한 경우

				if (temp_y == N) {
					//왼쪽만 탐색
					if (arr[temp_x][temp_y - 1]) {
						temp_y--;
					}//왼쪽에 길 있는 경우
				}//마지막줄인 경우
				else if (temp_y == 1) {
					//오른쪽만 탐색
					if (arr[temp_x][temp_y]) {
						temp_y++;
					}//오른쪽에 길 있는 경우
				}//첫번째줄인 경우
				else {
					if (arr[temp_x][temp_y - 1]) {
						temp_y--;
					}//왼쪽에 길 있는 경우
					else if (arr[temp_x][temp_y]) {
						temp_y++;
					}//오른쪽에 길 있는 경우
				}//첫째줄||마지막줄이 아닌 경우
				temp_x++;
			}//while문

			if (i != temp_y) {
				return;
			}//시작점과 도착점이 다른 경우
		}//1~N번까지 도는 i for문
		if (result == -1) {
			result = num;
		}
		else {
			result = min(result, num);
		}
		//check = true;

		return;
	}//탐색 시작
	else {
		for (int i = x; i <= H; i++) {
			for (int j = 1; j < N; j++) {
				if (i == x && j <= y) {
					continue;
				}//이전 배열 인덱스 continue
				if (arr[i][j]) {
					continue;
				}//이미 가로줄 있는 경우

				if (j == 1) {
					if (!arr[i][j + 1]) {
						arr[i][j] = 1;
						solve(i, j, cnt + 1, num);
						arr[i][j] = 0;
					}
				}
				else if (j == N - 1) {
					if (!arr[i][j - 1]) {
						arr[i][j] = 1;
						solve(i, j, cnt + 1, num);
						arr[i][j] = 0;
					}
				}
				else {
					if (!arr[i][j + 1] && !arr[i][j - 1]) {
						arr[i][j] = 1;
						solve(i, j, cnt + 1, num);
						arr[i][j] = 0;
					}
				}
			}//j for문
		}//i for문
	}//재귀(cnt!=num)
}//cnt==지금까지 고른 개수, num==골라야하는 개수

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int a, b;

	cin >> N >> M >> H;

	for (int i = 0; i < M; i++) {
		cin >> a >> b;

		arr[a][b] = 1;
	}//가로선 개수만큼 도는 for문

	//if (M == 0) {
	//	cout << 0;
	//}
	//else {

		for (int i = 1; i <= H; i++) {
			for (int j = 1; j < N; j++) {
				if (arr[i][j]) {
					continue;
				}//이미 가로줄 있는 경우

				if (!arr[i][j]) {
					if (j == 1) {
						if (arr[i][j + 1]) {
							continue;
						}
					}
					else if (j == N-1) {
						if (arr[i][j - 1]) {
							continue;
						}
					}
					else {
						if (arr[i][j + 1] || arr[i][j - 1]) {
							continue;
						}
					}
					solve(i, j, 0, 0);
					arr[i][j] = 1;
					solve(i, j, 1, 1);
					solve(i, j, 1, 2);
					solve(i, j, 1, 3);
					arr[i][j] = 0;
				}

			}//j for문
		}//i for문

		cout << result;
	//}
	return 0;
}

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

문제

문제

출처

ICPC

62%에서 틀렸습니다가 뜹니다

jsoomin0103 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말