[ C ] tromino

[ 문제 ]

A tromino is a group of three unit squares arranged in an L-shape. Consider the following tiling problem: The input is an array of unit squares where is a positive power of 2, with one forbidden square on the array. The output is a tiling of the array that satisfies the following conditions: Every unit square other than the input square is covered by a tromino. No tromino covers the input square. T(n) = 7T ( 5 + n ) 10n for n > 1 T(1) = 1 n S(n) = 2 n − 1 S(n) n m × m mCOMPUTER ALGORITHMS - HW #2 2 No two trominos overlap. No tromino extends beyond the board. Write a divide-and-conquer algorithm that solves this problem.

 

 

[ 해결 코드 ]

 

(미해결 ㅠ 에러가 조금 있는 것 같다ㅠㅠ)

 

#include<stdio.h>
#define m 128 //2^7
int arr[m][m];
int tile_num=0;
void put_tile(int x1, int y1,	int x2, int y2,
	int x3, int y3) {
	tile_num++;
	arr[x1][y1] = tile_num;
	arr[x2][y2] = tile_num;
	arr[x2][y2] = tile_num;
}

void calculate_tiling(int n, int x, int y) {
	int a=0, b=0;

	// 2*2 만 남았을 때 빈 칸 빼고 다 타일 놓기
	if (n == 2) {
		tile_num++;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (arr[x + i][y + i] == 0) {
					arr[x + i][y + i] = tile_num;	
				}
			}
		}
		return 0;
	}

	//빈 칸(a,b) 찾기
	for (int i = x; i < x + n; i++) {
		for (int j = y; j < y + n; j++) {
			if (arr[i][j] != 0) {
				a = i, b = j;
			}
		}
	}

	//2 1
	//3 4

	//빈 칸이 1사분면 (+,+)
	if (a >= x + (n / 2) && b >= y + (n / 2))
		put_tile(x + (n / 2) - 1, y + (n / 2),
			x + (n / 2), y + (n / 2) - 1,
			x + (n / 2) - 1, y + (n / 2) - 1);

	//빈 칸이 2사분면 (-, +)
	else if (a < x + (n / 2) && b >= y + (n / 2))
		put_tile(x + (n / 2), y + (n / 2) -1,
			x + (n / 2), y + (n / 2),
			x + (n / 2) - 1, y + (n / 2) - 1);


	//빈 칸이 3사분면 (-, -)
	else if (a < x + (n / 2) && b < y + (n / 2))
		put_tile(x + (n / 2), y + (n / 2) - 1,
			x + (n / 2), y + (n / 2),
			x + (n / 2) - 1, y + (n / 2) );


	//빈 칸이 4사분면 (+, -)
	else if (a >= x + (n / 2) && b < y + (n / 2))
		put_tile(x + (n / 2) -1, y + (n / 2),
			x + (n / 2), y + (n / 2),
			x + (n / 2) - 1, y + (n / 2) - 1);

	//divide and conquer
	calculate_tiling(n / 2, x, y + (n / 2));
	calculate_tiling(n / 2, x, y);
	calculate_tiling(n / 2, x + (n / 2), y);
	calculate_tiling(n / 2, x + (n / 2), y + (n / 2));

	return 0;
}

int main()
{
	//빈 셀
	arr[0][0] = -1;

	int n = 8; //128=2^7 -> 7+1=8
	calculate_tiling(n, 0, 0);

	//결과출력
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			printf("%d ",arr[i][j]);
		}
		printf("\n");
	}

	return 0;
}

 

 

[ 결과 ]

 

 

[ 참고 사이트 ]

www.geeksforgeeks.org/tiling-problem-using-divide-and-conquer-algorithm/

Tiling Problem using Divide and Conquer algorithm - GeeksforGeeks