0617 - Piese

Cerința

Considerăm o tablă de șah pătratică formată din 2n linii și 2n coloane, unde n este un număr natural nenul, formată din 2n*2n zone. Aceasta poate fi acoperită, cu excepția unei singure zone, cu piese în formă de L, fiecare piesă acoperind 3 zone. De exemplu, pentru n=2, o acoperire este următoarea, în care zona neagră este cea neacoperită de piese: Pentru n dat, determinați o modalitate de acoperire a tablei cu piese, astfel încât să nu se suprapună piesele și să rămână o singură zonă neacoperită.

Date de intrare

Programul citește de la tastatură numărul n

Date de ieșire

Programul va afișa pe ecran o matrice care reprezintă tabla, cu următoarele proprietăți:

• matricea va avea 2n linii și 2n coloane
• matricea va conține un singur element 0, reprezentând zona neacoperită
• fiecare piesă va fi marcată pe tablă prin trei elemente cu aceeași valoare, dispuse în formă de L
• oricare două piese de pe tablă vor fi marcate cu valori diferite
• piesele vor fi marcate cu valori naturale consecutive, începând cu 1
• fiecare linie a matricei va fi afișată pe câte o linie a ecranului, elementele de pe o linie fiind separate prin câte un spațiu

Restricții și precizări

• 1 ≤ n ≤ 10
• orice aranjare corectă a pieselor se ia în considerare

Exemplu 1

Intrare

2

Iesire

2 2 5 5
2 1 1 5
3 0 1 4
3 3 4 4

Rezolvare

<syntaxhighlight lang="python" line> def acopera_tabla(tabla, top, left, defect_row, defect_col, size, counter):

   if size == 2:
       # Plasează piesele L în funcție de poziția zonei neacoperite
       counter += 1
       if defect_row == top:
           if defect_col == left:
               tabla[top][left + 1] = counter
               tabla[top + 1][left] = counter
               tabla[top + 1][left + 1] = counter
           else:
               tabla[top][left] = counter
               tabla[top + 1][left] = counter
               tabla[top + 1][left + 1] = counter
       else:
           if defect_col == left:
               tabla[top][left] = counter
               tabla[top][left + 1] = counter
               tabla[top + 1][left + 1] = counter
           else:
               tabla[top][left] = counter
               tabla[top][left + 1] = counter
               tabla[top + 1][left] = counter
       return counter

   half = size // 2
   mid_row, mid_col = top + half, left + half

   # Plasează piesa L centrală
   counter += 1
   if defect_row < mid_row and defect_col < mid_col:
       tabla[mid_row - 1][mid_col] = counter
       tabla[mid_row][mid_col - 1] = counter
       tabla[mid_row][mid_col] = counter
   elif defect_row < mid_row and defect_col >= mid_col:
       tabla[mid_row - 1][mid_col - 1] = counter
       tabla[mid_row][mid_col - 1] = counter
       tabla[mid_row][mid_col] = counter
   elif defect_row >= mid_row and defect_col < mid_col:
       tabla[mid_row - 1][mid_col - 1] = counter
       tabla[mid_row - 1][mid_col] = counter
       tabla[mid_row][mid_col] = counter
   else:
       tabla[mid_row - 1][mid_col - 1] = counter
       tabla[mid_row - 1][mid_col] = counter
       tabla[mid_row][mid_col - 1] = counter

   # Apel recursiv pentru fiecare submatrice
   counter = acopera_tabla(tabla, top, left, defect_row, defect_col, half, counter)
   counter = acopera_tabla(tabla, top, mid_col, mid_row - 1, mid_col, half, counter)
   counter = acopera_tabla(tabla, mid_row, left, mid_row, mid_col - 1, half, counter)
   counter = acopera_tabla(tabla, mid_row, mid_col, mid_row, mid_col, half, counter)

   return counter

def afiseaza_tabla(tabla):

   for linie in tabla:
       print(" ".join(map(str, linie)))

def main():

   n = int(input().strip())
   
   N = 2 ** n
   tabla = [[0] * N for _ in range(N)]

   # Inițializați o singură zonă neacoperită
   defect_row, defect_col = 0, 0
   tabla[defect_row][defect_col] = -1

   acopera_tabla(tabla, 0, 0, defect_row, defect_col, N, 1)
   afiseaza_tabla(tabla)

if __name__ == "__main__":

   main()

</syntaxhighlight>