글 읽기 - 어디서 루프가 걸리는 걸까요??

swrho 3년 전 0

알고리즘은 5부터 시작해서 4 3 2 1 이렇게 백트래킹으로 탐색하였습니다.

고민을 많이 해봤는데 잘 모르겠네요.

#include<stdio.h>
#include<stdlib.h>
#include<algorithm>

using namespace std;

int map[11][11], visit[6], ans = 987654321;

void Fill (int x, int y, int size) {
	for (int i = x; i < x + size; i++)
		for (int j = y; j < y + size; j++)
			map[i][j] = 0;
}
void redueFill(int x, int y, int size) {
	for (int i = x; i < x + size; i++)
		for (int j = y; j < y + size; j++)
			map[i][j] = 1;
}
int ifAllFilled(void) {
	for (int i = 0; i < 10; i++) {
		for (int j = 0; j < 10; j++) {
			if (map[i][j] == 1) return 0;
		}
	}
	return 1;
}
int chkIfAvailable(int x, int y, int size) {
	for (int i = x; i < x + size; i++) {
		for (int j = y; j < y + size; j++) {
			if (map[i][j] == 0) return 0;
		}
	}
	return 1;
}
void bt(int cnt, int x, int y) {
	if (cnt >= ans) return;
	if (cnt > 25) return;
	if (ifAllFilled()) {
		ans = min(ans, cnt);
		return;
	}
	if (map[x][y] == 1) {
		for (int z = 5; z > 0; z--) {
			if (visit[z] == 5) continue;
			if (chkIfAvailable(x, y, z)) {
				visit[z]++;
				Fill(x, y, z);
				bt(cnt + 1, x, y + z);
				redueFill(x, y, z);
				visit[z]--;
			}
		}
	}
	if (x > 9)
		return;
	if (y > 9) {
		bt(cnt, x + 1, 0);
		return;
	}
	bt(cnt, x, y + 1);
}
int main() {
	for (int i = 0; i < 10; i++)
		for (int j = 0; j < 10; j++)
			scanf("%d", &map[i][j]);
	bt(0, 0, 0);
	if (ans == 987654321) printf("-1");
	else
		printf("%d", ans);
}

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

문제

문제

출처

ICPC

어디서 루프가 걸리는 걸까요??

swrho 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말