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

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

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.