Responsive image
Meniu
Toate soluțiile
Soluţii trimise de tine
Compilator online
Ajutor

Algoritmul lui Lee

Adăugată de :
sorynsoo
Sursă :
IronCoders
Autor :
sorynsoo
Grupă :
Medie
Punctaj :
0 pc

Restricţii

Citire / Scriere :
stdin, stdout
Limită timp :
100 ms
Limită memorie :
1024 kbytes

Este un algoritm care foloseste o coada pentru determinarea unui numar minim de pasi intre 2 sau mai multe puncte cheie,  gasirea drumului cel mai scurt de iesire dintr-un labirint sau alte cazuri asemanatoare. 

Pasi necesari :

Se incepe algoritmul prin adaugarea in coada a pozitiei de incepere apoi :

  1. Se scoate din coada o pozitie.
  2. Se cauta o noua pozitie valida in care se poate ajunge din locatia curenta , odata gasita este adaugata in coada si se reia punctul 1 pana este indeplinita cerinta. 

 

Cerinta

Se da un tablou bidimensional cu N linii si coloane si 2 puncte cheie, sa se calculeze numarul minim de pasi necesar parcurgerii unui drum intre cele 2 puncte.

La fiecare pas se poate executa o mutare in urmatoarele directii  Nord, Sud, West si Est atat timp cat casuta respectiva este libera.

 

Date intrare

Pe prima linie se afla numarul .

Pe a 2-a linie se afla 4 numere, Xstart, Ystart, Xfinal, Yfinal  , avand urmatorul format ( linie, coloana ) .

Pe urmatoarele N linii se afla N numere reprezentand elementele tabloului bidimensional , cifra 1 daca casuta este libera trecerii sau cifra 0 in caz contrar.

 

Date iesire

Pe prima linie va fi afisat numarul minim de pasi necesari sau valoarea -1 daca nu exista niciun drum intre cele doua puncte .

 

Restrictii:

N <=100

 

Rezovare: Click

 

Exemplu

  Date intrare   Date iesire
  4
  1 1 4 4
  1 1 1 0
  1 0 1 0
  1 0 1 1
  1 0 0 1
 6

 


Trimite o solutie

Format: cpp şi c

Selectează runda

Trebuie să fii logat pentru a trimite surse


Indicații rezolvare

Lee


Comentarii

Adauga un comentariu: Click !