Aurelia Raluca: Pagină nouă: = 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...

2024-03-23T00:13:39Z

Pagină nouă: = Cerinţa = Se consideră o tablă de şah cu <code>n</code> linii şi <code>m</code> 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 <code>n</code> linii și <code>m</code> coloane, fiecare element...

New page

= Cerinţa =
Se consideră o tablă de şah cu <code>n</code> linii şi <code>m</code> 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 <code>n</code> linii și <code>m</code> coloane, fiecare element al matricei având valoarea pasului la care se ajunge în acel element, sau <code>0</code>, dacă nu s-a ajuns.

= Date de intrare =
Fișierul de intrare <code>saritura_calului1IN.txt</code> conține numerele <code>n</code> şi <code>m</code> , apoi numere <code>x y</code>, 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 <code>saritura_calului1OUT.txt</code> va conține <code>n</code> linii cu câte <code>m</code> numere naturale cuprinse între <code>1</code> și <code>n*m</code>, 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 =

* <code>1 ≤ n,m ≤ 100</code>
* <code>1 ≤ istart ≤ n</code>
* <code>1 ≤ jstart ≤ m</code>
* 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 =
<code>saritura_calului1IN.txt</code>
4 5 1 1
<code>saritura_calului1OUT.txt</code>
1 12 7 16 3
6 17 2 11 8
13 10 19 4 15
18 5 14 9 20

= Exemplul 2 =
<code>saritura_calului1IN.txt</code>
101 5 1 1
<code>saritura_calului1OUT.txt</code>
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>

0384 - Saritura Calului 1 - Revision history