Editing 0865 - Palat

==Cerința==

Ileana Cosânzeana se mărită. În consecință a dat sfoară-n țară și au venit mai mulți Feți-Frumoși, dornici să primească mâna fetei, împreună cu palatul în care locuiește. Acesta este alcătuit din '''n*m''' camere, dispuse sub forma unei matrice cu '''n''' linii și '''m''' coloane.

În anumite camere nu se poate intra, deoarece acolo se află zmei răi. În celelalte se poate intra; mai precis se poate trece dintr-o cameră în altă cameră dacă se învecinează pe linie sau pe coloană. În una dintre camere se află Ileana Cosânzeana, iar în alte camere se afla câte un Făt-Frumos. Aceștia pot trece dintr-o cameră în alta, cu condiția să nu intre într-o cameră care conține un zmeu. Trecerea dintr-o cameră în alta a unui Făt-Frumos durează un minut.

Alegerea celui care va primi mâna Ilenei se face pe principiul '''primul venit, primul servit''' (suntem la capitolul '''Coada'''). Mai precis, se va căsători cu Ileana Cosânzeana acel Făt Frumos care ajunge primul la ea. Dacă ajung la Ileana Cosânzeana mai mulți Feți-Frumoși în același timp, deoarece este interzisă poligamia, Ileana se va căsători cu Făt-Frumos care la început era situat cât mai jos (pe o linie cu indice cât mai mare). Dacă mai mulți Feți-Frumoși situați pe aceeași linie ajung în timp minim la Ileana, aceasta se va căsători cu cel care era cât mai la dreapta (pe o coloană cu indice cât mai mare).

Aflați poziția inițială a lui Făt-Frumos care va primi mâna fetei.

==Date de intrare==

Fișierul de intrare '''palatin.txt''' conține pe prima linie numerele '''n m''', iar următoarele '''n''' linii câte '''m''' caractere, care pot fi:

*'''Z''' – reprezintă o cameră ocupată de un zmeu
*'''I''' – reprezintă camera în care se află Ileana Cosânzeana
*'''F''' – reprezinta o cameră în care se află un Făt-Frumos
*'''_''' – reprezintă o cameră liberă

==Date de ieșire==

Fișierul de ieșire '''palatout.txt''' va conține pe prima linie două numere '''i j''', separate prin exact un spațiu, reprezentând coordonatele (linie coloană) ale camerei în care se afla acel Făt-Frumos care va primi mâna Ilenei.

==Restricții și precizări==

*'''1 ≤ n ≤ 1000'''
*'''1 ≤ m ≤ 1000'''
*liniile și coloanele sunt numerotate de la '''1'''

==Exemplul 1:==

'''palatin.txt'''

 4 5
 ZF_ZF
 _Z_Z_
 _I___
 _Z_ZF

'''palatout.txt'''

 Datele de intrare corespund restrictiilor impuse
 4 5

==Exemplul 2:==

'''palatin.txt'''

 palat

'''palatout.txt'''

 Datele de intrare nu corespund restrictiilor impuse

==Rezolvare==

<syntaxhighlight lang="python" line="1" start="1">

from collections import deque


def validare(n_linii, m_coloane, matrice):           # functia de validare a datelor de intrare
    if n_linii > 1000 or m_coloane > 1000:
        raise ValueError

    for linie in matrice:
        if len(linie) != m_coloane:
            raise ValueError

    file_out.write("Datele de intrare corespund restrictiilor impuse\n")


def bfs(n_linii, m_coloane, matrice, inceput):                     # functia de rezolvare
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]
    q = deque([inceput])
    distanta = [[0] * m_coloane for _ in range(n_linii)]
    while q:
        x, y = q.popleft()
        for camera_i in range(4):
            nx, ny = x + dx[camera_i], y + dy[camera_i]
            if 0 <= nx < n_linii and 0 <= ny < m_coloane and matrice[nx][ny] != 'Z' and not distanta[nx][ny]:
                distanta[nx][ny] = distanta[x][y] + 1
                q.append((nx, ny))
    return distanta


if __name__ == '__main__':
    file_in = open("palatin.txt", "r")         # declararea fisierelor
    file_out = open("palatout.txt", "w")       # fisierul out trebuie declarat cu optiunea "w" (write)

    try:
        n, m = map(int, file_in.readline().split())
        mat = [list(file_in.readline().strip()) for _ in range(n)]
        start = None
        for i in range(n):
            for j in range(m):
                if mat[i][j] == 'I':
                    start = (i, j)
                    break
            if start:
                break

        validare(n, m, mat)                 # apelul functiei de validare
        dist = bfs(n, m, mat, start)        # apelul functiei de rezolvare

        min_dist = min_pos = None
        for i in range(n-1, -1, -1):
            for j in range(m-1, -1, -1):
                if mat[i][j] == 'F' and (min_dist is None or dist[i][j] < min_dist and dist[i][j] != 0):
                    min_dist = dist[i][j]
                    min_pos = (i+1, j+1)

        file_out.write(f"{min_pos[0]} {min_pos[1]}\n")

    except ValueError:
        file_out.write("Datele de intrare nu corespund restrictiilor impuse")
    except IndexError:
        file_out.write("Datele de intrare nu corespund restrictiilor impuse")

</syntaxhighlight>

==Explicație==

În palat se află trei Feți Frumoși. Doi dintre ei ajung la Ileana Cosânzeana în '''3''' minute, al treilea în '''4''' minute.