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.