我正在尝试解决n x n板的Tromino平铺问题。给定n x n板上缺少x和y的方形坐标(MS),我们必须用'L'形瓷砖填充板的其余部分。
我设法获得2 x 2板的输出。但是,我对4 x 4、8 x 8 ...等电路板尺寸的输出感到困惑。
以下是我编写的以递归方式调用自己来印刷电路板的函数:
/* This program tiles with right trominoes an nxn
board with one square missing, assuming that n
is a power of 2. */
#include <stdio.h>
#include <stdlib.h>
// #define LR 0
// #define LL 1
// #define UR 3
// #define UL 2
// #define MS -1
const int Max = 256;
int board[Max][Max];
void tromino /* function to do tiling */
( int x_board, /* x coordinate of board */
int y_board, /* y coordinate of board */
int x_missing, /* x coordinate of missing square */
int y_missing, /* y coordinate of missing square */
int board_size); /* size of board */
void show_Tromino(int size, int x_miss, int y_miss);
int main()
{
int board_size,
x_missing, /* x coordinate of missing square */
y_missing; /* y coordinate of missing square */
do {
printf( "\n-------------------------------------" );
printf( "\nEnter size of board (0 to quit): " );
scanf( "%d", &board_size );
if ( board_size ) {
printf( "\nEnter coordinates of missing square: " );
scanf( "%d%d", &x_missing, &y_missing );
printf( "\n\nTiling\n" );
// if(board[x_board][0] == x_missing && board[0][y_board] == y_missing)
// printf("MS\t");
//board[x_missing][y_missing] = -1;
tromino( 0, 0, x_missing, y_missing, board_size);
show_Tromino(board_size, x_missing, y_missing);
}
} while ( board_size );
return EXIT_SUCCESS;
}
void tromino( int x_board, /* x coordinate of board */
int y_board, /* y coordinate of board */
int x_missing, /* x coordinate of missing square */
int y_missing, /* y coordinate of missing square */
int board_size) /* size of board */
{
int half_size = board_size/2, /* size of subboard */
x_center, /* x coordinate of center of board */
y_center, /* y coordinate of center of board */
x_upper_left, /* x coordinate of missing square in upper
left subboard */
y_upper_left, /* y coordinate of missing square in upper
left subboard */
x_upper_right, /* x coordinate of missing square in upper
right subboard */
y_upper_right, /* y coordinate of missing square in upper
right subboard */
x_lower_right, /* x coordinate of missing square in lower
right subboard */
y_lower_right, /* y coordinate of missing square in lower
right subboard */
x_lower_left, /* x coordinate of missing square in lower
left subboard */
y_lower_left; /* y coordinate of missing square in lower
left subboard */
if ( board_size == 2 ) /* 2x2 board */
{
for(int i=board_size-1; i>=0; i--)
{
for(int j=0;j<board_size;j++)
{
if(i==x_missing && j==y_missing)
//printf("MS\t");
{ board[i][j] = -1;}
//printf( "%d %d ", x_board + 1, y_board + 1 );
/* find and print orientation of tromino */
if(x_missing == x_board)
{
if(y_missing == y_board)
// printf("UR\t");
{board[i][j] = 2;}
else
// printf("LR\t");
{board[i][j] = 0;}
}
else
{
if(y_missing == y_board)
// printf("UL\t");
{board[i][j] = 3;}
else
// printf("LL\t");
{board[i][j] = 1;}
}
}
printf("\n");
}
return;
}
// if(board_size>2)
// { /* compute x and y coordinates of center of board */
x_center = x_board + half_size;
y_center = y_board + half_size;
if((x_missing < x_center) && (y_missing < y_center))
{
//printf("UR\t");
x_upper_left = x_center - 1;
y_upper_left = y_center;
x_upper_right = x_center;
y_upper_right = y_center;
x_lower_left = x_missing;
y_lower_left = y_missing;
x_lower_right = x_center;
y_lower_right = y_center - 1;
}
if((x_missing >= x_center) && (y_missing < y_center))
{
//printf("UL\t");
x_upper_left = x_center - 1;
y_upper_left = y_center;
x_upper_right = x_center;
y_upper_right = y_center;
x_lower_left = x_center - 1;
y_lower_left = y_center - 1;
x_lower_right = x_missing;
y_lower_right = y_missing;
}
if((x_missing >= x_center) && (y_missing >= y_center))
{
//printf("LL\t");
x_upper_left = x_center - 1;
y_upper_left = y_center;
x_upper_right = x_missing;
y_upper_right = y_missing;
x_lower_left = x_center - 1;
y_lower_left = y_center - 1;
x_lower_right = x_center;
y_lower_right = y_center - 1;
}
if((x_missing < x_center) && (y_missing >= y_center))
{
//printf("LR\t");
x_upper_left = x_missing;
y_upper_left = y_missing;
x_upper_right = x_center;
y_upper_right = y_center;
x_lower_left = x_center - 1;
y_lower_left = y_center - 1;
x_lower_right = x_center;
y_lower_right = y_center - 1;
}
/* tile the four subboards */
tromino( x_board, y_board + half_size,
x_upper_left, y_upper_left, half_size);
tromino( x_board + half_size, y_board + half_size,
x_upper_right, y_upper_right, half_size);
tromino( x_board + half_size, y_board,
x_lower_right, y_lower_right, half_size);
tromino( x_board, y_board,
x_lower_left, y_lower_left, half_size);
}
void show_Tromino(int size, int x_miss, int y_miss)
{
int bsize[Max][Max];
for(int i=size-1; i>=0;i--)
{
for(int j=0; j<size;j++)
{
if(!(bsize[i][j] == -1 || (j==x_miss && i==y_miss)))
{
if(bsize[i][j] == 1)
{
printf("LL\t");
}
else if(bsize[i][j] == 2)
{
printf("UL\t");
}
else if(bsize[i][j] == 3)
{
printf("UR\t");
}
else if(bsize[i][j] == 0)
{
printf("LR\t");
}
}
else if (bsize[i][j] == -1 || (j==x_miss && i==y_miss))
{
printf("MS\t");
}
bsize[i][j] += 1;
}
printf("\n");
}
}
output1:当电路板尺寸为2 x 2(正确)时
Enter size of board (0 to quit): 2
Enter coordinates of missing square: 0 1
Tiling
------
MS LR
LR LR
output2:当板子尺寸为4 x 4(不正确)时。不过,我正在找到Missing Square(MS)的正确位置。
Enter size of board (0 to quit): 4
Enter coordinates of missing square: 0 1
Tiling
------
LR LR LR LR
LR LR LR LR
MS LR LR LR
LR LR LR LR
output2:当电路板尺寸为4 x 4(预期)时>
Enter size of board (0 to quit): 4 Enter coordinates of missing square: 0 1 Tiling ------ UL UL UR UR UL UR UR UR MS LR UR LR LR LR LR LR
注意:
我正在尝试解决n x n板的Tromino平铺问题。给定n x n木板中缺少x和y的方形坐标(MS),我们必须用'L'形瓷砖填充木板的其余部分。我有...
问题是由于基本情况造成的。在求解2x2时,您忘记考虑偏移量了。每次仅更新[0,0],[0,1],[1,0],[1,1]。其余的值(缺少的图块除外)保存着垃圾值。