Drum Descriere
1
Liceul Teoretic de Informatică „Grigore Moisil” Iaşi CONCURS NAŢIONAL DE INFORMATICĂ Clasa a IX -a Problema 1 – drum Autor: Ştefan Negruş Descrierea soluţiei (Ştefan Negruş) Soluţie 100 puncte – O(N*M) Iniţial, matricea din enunţ va conţine numai valori de 0. Pe măsură ce citim poziţiile pe care se află densităţile, completăm matricea astfel: În primul rând, decodificăm poziţia pentru a obţine linia x şi coloana y pe care trebuie asezată densitatea. În loc să punem în matrice valoarea citită, vom plasa una din valorile {1,2,3} cu semnificaţia: Mat[x][y]=1 există drum de la locaţia [x][y] la linia 1 Mat[x][y]=2 există drum de la locaţia [x][y] la linia N Mat[x][y]=3 nu am descoperit încă dacă există drum de la locaţia [x][y] la linia 1sau la linia N Dacă x=1 atunci Mat[x][y]=1 Dacă x=N atunci Mat[x][y]=2 Dacă nu suntem in primele 2 cazuri atunci Mat[x][y]=3 Dacă în urma acestor adaugări în matrice se creează una dintre situaţiile: Mat[x][y]=1 şi unul din vecini are valoarea 2 sau Mat[x][y]=2 şi unul din vecini are valoarea 1 sau Mat[x][y] are atât un vecin 1 cât şi un vecin 2, însemnă că am aflat răspunsul. Oricare dintre aceste 3 situaţii reprezintă faptul că din locaţia [x][y] există drum atât la linia 1 cât şi la linia N, deci am găsit un drum de la la linia 1 la linia N. Prin urmare, afişăm densitatea corespunzatoare liniei de pe care tocmai am citit (densităţile sunt considerate in ordine crescătoare). Altfel, actualizăm matricea astfel: Dacă în matrice există o valoare 3 vecină cu o valoare 1, punem in loc de 3, valoarea 1. Dacă în matrice există o valoare 3 vecină cu o valoare 2, punem in loc de 3, valoarea 2. Dacă în locaţia [x][y] am plasat valoarea 1 sau valoarea 2, înlocuim valorile 3 din vecinătate cu marcajul Mat[x][y], continuând cu vecinii vecinilor, cât timp acest lucru este posibil.
description
uu
Transcript of Drum Descriere
Liceul Teoretic de Informatică „Grigore Moisil” Iaşi
CONCURS NAŢIONAL DE INFORMATICĂ Clasa a IX-a
Problema 1 – drum Autor: Ştefan Negruş Descrierea soluţiei (Ştefan Negruş) Soluţie 100 puncte – O(N*M) Iniţial, matricea din enunţ va conţine numai valori de 0. Pe măsură ce citim poziţiile pe care se află densităţile, completăm matricea astfel: În primul rând, decodificăm poziţia pentru a obţine linia x şi coloana y pe care trebuie asezată densitatea. În loc să punem în matrice valoarea citită, vom plasa una din valorile {1,2,3} cu semnificaţia: Mat[x][y]=1 există drum de la locaţia [x][y] la linia 1 Mat[x][y]=2 există drum de la locaţia [x][y] la linia N Mat[x][y]=3 nu am descoperit încă dacă există drum de la locaţia [x][y] la linia 1sau la linia N Dacă x=1 atunci Mat[x][y]=1 Dacă x=N atunci Mat[x][y]=2 Dacă nu suntem in primele 2 cazuri atunci Mat[x][y]=3 Dacă în urma acestor adaugări în matrice se creează una dintre situaţiile:
Mat[x][y]=1 şi unul din vecini are valoarea 2 sau Mat[x][y]=2 şi unul din vecini are valoarea 1 sau Mat[x][y] are atât un vecin 1 cât şi un vecin 2,
însemnă că am aflat răspunsul. Oricare dintre aceste 3 situaţii reprezintă faptul că din locaţia [x][y] există drum atât la linia 1 cât şi la linia N, deci am găsit un drum de la la linia 1 la linia N. Prin urmare, afişăm densitatea corespunzatoare liniei de pe care tocmai am citit (densităţile sunt considerate in ordine crescătoare). Altfel, actualizăm matricea astfel: Dacă în matrice există o valoare 3 vecină cu o valoare 1, punem in loc de 3, valoarea 1. Dacă în matrice există o valoare 3 vecină cu o valoare 2, punem in loc de 3, valoarea 2. Dacă în locaţia [x][y] am plasat valoarea 1 sau valoarea 2, înlocuim valorile 3 din vecinătate cu marcajul Mat[x][y], continuând cu vecinii vecinilor, cât timp acest lucru este posibil.
