0384 - Saritura Calului 1

Cerinţa

Se consideră o tablă de şah cu n linii şi m coloane. La o poziţie dată se află un cal de şah, acesta putându-se deplasa pe tablă în modul specific acestei piese de şah (în L).

Să se determine o modalitate de parcurgere a tablei de către calul dat, astfel încât acesta să nu treacă de două ori prin aceeaşi poziţie. Parcurgerea constă într-o matrice cu n linii și m coloane, fiecare element al matricei având valoarea pasului la care se ajunge în acel element, sau 0, dacă nu s-a ajuns.

Date de intrare

Fișierul de intrare saritura_calului1IN.txt conține numerele n şi m , apoi numere x y, reprezentând dimensiunile tablei (numărul de linii şi numărul de coloane) , respectiv coordonatele iniţiale ale calului (linie, coloana).

Date de ieşire

Fișierul de ieșire saritura_calului1OUT.txt va conține n linii cu câte m numere naturale cuprinse între 1 și n*m, separate prin exact un spațiu, reprezentând parcurgerea solicitată. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

Restricţii şi precizări

• 1 ≤ n,m ≤ 100
• 1 ≤ istart ≤ n
• 1 ≤ jstart ≤ m
• scorul obținut pe fiecare test este proporțional cu gradul de acoperire a tablei. Astfel, dacă tabla este acoperită în întregime, se acordă 100% din punctaj. Dacă tabla este acoperită în proporție de 70%, se acordă 70% din punctaj, etc.

Exemplul 1

saritura_calului1IN.txt

4 5 1 1

saritura_calului1OUT.txt

1 12 7 16 3 
6 17 2 11 8 
13 10 19 4 15 
18 5 14 9 20

Exemplul 2

saritura_calului1IN.txt

101 5 1 1

saritura_calului1OUT.txt

Datele nu corespund restrictiilor impuse

Rezolvare

<syntaxhighlight lang="python3" line="1"> def mutare_valida(tabla, vizitat, i, j, n, m):

   return 0 <= i < n and 0 <= j < m and not vizitat[i][j]

def cal_tura(tabla, vizitat, i, j, n, m, contor_mutari):

   di = [-1, -2, -2, -1, 1, 2, 2, 1]
   dj = [-2, -1, 1, 2, 2, 1, -1, -2]

   tabla[i][j] = contor_mutari
   vizitat[i][j] = True
   if contor_mutari == n * m:
       return True
   
   for k in range(8):
       ni = i + di[k]
       nj = j + dj[k]
       if mutare_valida(tabla, vizitat, ni, nj, n, m):
           if cal_tura(tabla, vizitat, ni, nj, n, m, contor_mutari + 1):
               return True
   
   tabla[i][j] = 0
   vizitat[i][j] = False
   return False

def verificare_restrictii(n, m, istart, jstart):

   if not (1 <= n <= 100 and 1 <= m <= 100 and 1 <= istart <= n and 1 <= jstart <= m):
       return False
   return True

def afisare_tabla(tabla, fout):

   for row in tabla:
       fout.write(' '.join(map(str, row)) + '\n')

if __name__ == "__main__":

   fin = open("saritura_calului1IN.txt", "r")
   fout = open("saritura_calului1OUT.txt", "w")

   n, m, istart, jstart = map(int, fin.readline().split())
   
   if not verificare_restrictii(n, m, istart, jstart):
       fout.write("Datele nu corespund restrictiilor impuse")
   else:
       tabla = [[0] * m for _ in range(n)]
       vizitat = [[False] * m for _ in range(n)]
       
       if cal_tura(tabla, vizitat, istart - 1, jstart - 1, n, m, 1):
           afisare_tabla(tabla, fout)
       else:
           fout.write("Nu există soluție!")
   
   fin.close()
   fout.close()

</syntaxhighlight>