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

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()