0726 - Acoperire 1

Dintr-o suprafaţă pătrată cu latura de N unităţi care este formată din N*N pătrăţele cu latura de o unitate se decupează cele 4 pătrăţele din colţuri.

Cerința

Determinaţi o modalitate de a acoperi suprafaţa în întregime cu piese de arie 4 unităţi care au forma următoare:

Piesele pot fi si rotite sau întoarse putând astfel să folosim toate cele 8 moduri de a le aşeza.

Date de intrare

Fișierul de intrare acoperire1.in conține pe prima linie un număr natural N, cu semnificaţia din enunţ.

Date de ieșire

Fișierul de ieșire acoperire1.out va conține valoarea -1 pe prima linie dacă problema nu are soluţie, iar în caz contrar va avea următoarea structură: N linii cu câte N valori fiecare reprezentând codificarea suprafeţei. Numerele de pe aceeaşi linie sunt separate prin câte un spaţiu. Poziţiile ocupate de prima piesă aşezată se vor codifica cu 1, poziţiile ocupate de a doua piesă aşezată se vor codifica cu 2 etc. Corespunzător colţurilor lipsă se va scrie valoarea 0.

Restricții și precizări

• 6 ≤ n ≤ 200
• Piesele trebuie să fie complet în interiorul zonei;
• Zona trebuie acoperită integral;
• Două piese nu se pot suprapune complet sau parţial;

Exemplu:

acoperire1.in

6

acoperire1.out

0 7 2 2 2 0 
3 7 2 4 4 4 
3 7 7 4 5 5 
3 3 6 1 1 5 
6 6 6 8 1 5 
0 8 8 8 1 0

<syntaxhighlight lang="python" line="1"> def place_l_tiles(board, n, top_left_row, top_left_col):

   # n - dimension of the current board (n x n)
   if n == 2:
       # Base case: only one tile can fit, as 4 cells are considered and one corner is missing
       for i in range(2):
           for j in range(2):
               if board[top_left_row + i][top_left_col + j] == 0:
                   board[top_left_row + i][top_left_col + j] = 1
       return
   
   half = n // 2
   # Find the center tile to place the L-shaped tromino around
   # (middle of the top-left, top-right, bottom-left, bottom-right quarters)
   center_r, center_c = top_left_row + half - 1, top_left_col + half - 1

   # Determine which quadrant is missing the corner cell
   if board[top_left_row][top_left_col] == -1:
       missing_quad = 0
   elif board[top_left_row][top_left_col + n - 1] == -1:
       missing_quad = 1
   elif board[top_left_row + n - 1][top_left_col] == -1:
       missing_quad = 2
   elif board[top_left_row + n - 1][top_left_col + n - 1] == -1:
       missing_quad = 3
   
   # Fill the center of the current board with a L-shaped tromino
   tiles = [(center_r, center_c), (center_r, center_c + 1), (center_r + 1, center_c), (center_r + 1, center_c + 1)]
   # We have four quadrants (0: top-left, 1: top-right, 2: bottom-left, 3: bottom-right)
   for idx, (i, j) in enumerate(tiles):
       if idx != missing_quad:
           board[i][j] = 1

   # Recursively fill each of the four quadrants
   # Top-left quadrant
   place_l_tiles(board, half, top_left_row, top_left_col)
   # Top-right quadrant
   place_l_tiles(board, half, top_left_row, top_left_col + half)
   # Bottom-left quadrant
   place_l_tiles(board, half, top_left_row + half, top_left_col)
   # Bottom-right quadrant
   place_l_tiles(board, half, top_left_row + half, top_left_col + half)

1. Initialize the board

N = 4 # Example value, should be a power of 2 board = [[0 for _ in range(N)] for _ in range(N)]

1. Remove corners

board[0][0] = -1 board[0][N-1] = -1 board[N-1][0] = -1 board[N-1][N-1] = -1

1. Place L-shaped tiles starting from the top-left corner of the board

place_l_tiles(board, N, 0, 0)

1. Print the board

for row in board:

   print(' '.join(str(cell) for cell in row))

</syntaxhighlight>