https://wiki.universitas.ro/index.php?action=history&feed=atom&title=3404_-_castel3 2026-05-01T06:37:18Z Revision history for this page on the wiki MediaWiki 1.42.1 https://wiki.universitas.ro/index.php?title=3404_-_castel3&diff=9704&oldid=prev 2024-03-22T20:53:49Z

<p></p> <a href="//wiki.universitas.ro/index.php?title=3404_-_castel3&amp;diff=9704&amp;oldid=9303">Show changes</a>

Aurelia Raluca https://wiki.universitas.ro/index.php?title=3404_-_castel3&diff=9303&oldid=prev 2024-01-09T08:46:30Z

<p>Pagină nouă: == Enunt == Înspăimântătorii tăi luptători au răpit-o pe Prinţesa Ghiocela şi au închis-o în castelul tău de pe vârful Muntelui Pleşuv. Deoarece eşti un geniu malefic, te-ai hotărât să îi oferi prinţesei iluzia unei şanse de evadare. Castelul tău are forma unui caroiaj cu M linii şi N coloane. Cele M x N celule ale castelului sunt numerotate de la 1 la M x N în ordinea parcurgerii caroiajului pe linii de sus în jos, iar pe aceeaşi linie în ordinea...</p> <p><b>New page</b></p><div>== Enunt ==<br /> <br /> Înspăimântătorii tăi luptători au răpit-o pe Prinţesa Ghiocela şi au închis-o în castelul tău de pe vârful Muntelui Pleşuv. Deoarece eşti un geniu malefic, te-ai hotărât să îi oferi prinţesei iluzia unei şanse de evadare.<br /> Castelul tău are forma unui caroiaj cu M linii şi N coloane. Cele M x N celule ale castelului sunt numerotate de la 1 la M x N în ordinea parcurgerii caroiajului pe linii de sus în jos, iar pe aceeaşi linie în ordinea coloanelor de la stânga la dreapta. În fiecare dintre celulele castelului ai pus câte o cheie, mai precis celula i conţine cheia cu numărul i. Evident, pentru a intra într-o cameră, prinţesa are nevoie de o anume cheie care permite deschiderea acesteia. Mai mult, dintr-o cameră prinţesa se poate deplasa într-un moment numai într-una dintre cele maximum patru camere adiacente pe orizontală şi verticală, doar dacă deţine cheia necesară deschiderii sale. Odată ce a intrat într-o cameră şi a obţinut o cheie, prinţesa o păstrează şi poate să o utilizeze ori de câte ori doreşte.<br /> <br /> == Cerinta ==<br /> <br /> Deşi eşti convins că prinţesa nu va scăpa din castel, eşti curios să afli câte dintre cele M x N camere îi sunt accesibile. Date fiind dimensiunile castelului, camera în care se află iniţial prinţesa şi cheile necesare deschiderii fiecăreia dintre camere, află răspunsul la această întrebare presantă.<br /> <br /> == Date de intrare ==<br /> <br /> Fișierul de intrare castel.in conţine pe prima linie trei numere naturale M N K separate prin câte un spaţiu reprezentând dimensiunile castelului, respectiv numărul camerei în care se află iniţial prinţesa. Urmează descrierea castelului. Pe fiecare dintre următoarele M linii se află câte N numere naturale cuprinse între 1 şi M x N reprezentând cheile necesare deschiderii fiecăreia dintre camere.<br /> <br /> == Date de ieșire ==<br /> <br /> Fișierul de ieșire castel.out va conţine o singură linie pe care va fi scris un singur număr natural reprezentând numărul de camere accesibile prinţesei.<br /> <br /> == Restricții și precizări ==<br /> <br /> *1 ≤ M, N ≤ 150<br /> *1 ≤ K ≤ M * N<br /> *Odată ce prinţesa a păşit într-o cameră, respectiva cameră va rămâne pentru totdeauna deschisă.<br /> <br /> == Exemplul 1 ==<br /> <br /> ;castelin.txt<br /> <br /> :4 3 1<br /> <br /> :1 1 4<br /> <br /> :1 6 2<br /> <br /> :6 9 8<br /> <br /> :12 10 11<br /> <br /> ;castelout.txt<br /> <br /> :Datele introduse corespund restrictiilor impuse.<br /> <br /> :7<br /> <br /> == Exemplul 2 ==<br /> <br /> ;castelin.txt<br /> <br /> :0 8 9<br /> <br /> :-2 -3 -4<br /> <br /> :123 433 4322<br /> <br /> :9383 -12 -2<br /> <br /> :-098 -9087 0<br /> <br /> ;castelout.txt<br /> <br /> :Datele de intrare nu corespund restrictiilor impuse.<br /> <br /> == Rezolvare ==<br /> <br /> &lt;syntaxhighlight lang=&quot;python3&quot; line=&quot;1&quot;&gt;<br /> <br /> def numar_camere_accesibile(M, N, camera_initiala, chei_necesare):<br /> # Pasul 1: Construirea grafului<br /> graf = construieste_graf(M, N, chei_necesare)<br /> <br /> # Pasul 2: Căutarea în graf<br /> chei_prințesa = set()<br /> camere_accesibile = set()<br /> <br /> def dfs(camera):<br /> nonlocal chei_prințesa, camere_accesibile<br /> camere_accesibile.add(camera)<br /> <br /> for vecin in graf[camera]:<br /> cheie_necesara = graf[camera][vecin]<br /> if cheie_necesara in chei_prințesa:<br /> if vecin not in camere_accesibile:<br /> dfs(vecin)<br /> <br /> dfs(camera_initiala)<br /> <br /> # Pasul 3: Numărăm camerele accesibile<br /> return len(camere_accesibile)<br /> <br /> def construieste_graf(M, N, chei_necesare):<br /> graf = {}<br /> for i in range(1, M * N + 1):<br /> graf[i] = {}<br /> <br /> for i in range(1, M + 1):<br /> for j in range(1, N + 1):<br /> camera = (i - 1) * N + j<br /> <br /> # Verificăm camerele adiacente pe orizontală și verticală<br /> if i &gt; 1:<br /> vecin = camera - N<br /> cheie = chei_necesare[vecin - 1]<br /> graf[camera][vecin] = cheie<br /> graf[vecin][camera] = cheie<br /> <br /> if i &lt; M:<br /> vecin = camera + N<br /> cheie = chei_necesare[camera - 1]<br /> graf[camera][vecin] = cheie<br /> graf[vecin][camera] = cheie<br /> <br /> if j &gt; 1:<br /> vecin = camera - 1<br /> cheie = chei_necesare[vecin - 1]<br /> graf[camera][vecin] = cheie<br /> graf[vecin][camera] = cheie<br /> <br /> if j &lt; N:<br /> vecin = camera + 1<br /> cheie = chei_necesare[camera - 1]<br /> graf[camera][vecin] = cheie<br /> graf[vecin][camera] = cheie<br /> <br /> return graf<br /> <br /> rezultat = numar_camere_accesibile(M, N, camera_initiala, chei_necesare)<br /> print(rezultat)<br /> <br /> &lt;/syntaxhighlight&gt;</div>

Aurelia Raluca