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

Harta

Adăugată de :
sorynsoo
Sursă :
OLI2014 Brasov
Autor :
-
Grupă :
Medie
Punctaj :
0 pc

Restricţii

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

Piticot se află într-o pădure. Pădurea are formă de pătrat cu latura de n metri. Piticot are o hartă a pădurii şi a trasat pe hartă un caroiaj care împarte pădurea în nXn zone pătrate cu latura de 1 metru, zonele fiind numerotate pe linie, respectiv pe coloană, de la 1.

Pentru fiecare zonă de pe hartă şi-a notat timpul de parcurgere deoarece pădurea are diverse obstacole.

Piticot vrea să traverseze pădurea din colţul stânga sus (NV) şi parcurge pădurea spre colţul din dreapta jos (SE) astfel încât timpul de parcurgere să fie minim, ştiind că Piticot se poate deplasa în toate direcţiile.

Piticot vrea să ajungă în zona din pădure în care se găseşte o comoară, el recunoaşte această zonă de pe hartă după un număr secret care este notat pe spatele hărţii în format binar.

Determinaţi timpul minim de parcurgere a pădurii către comoară şi traseul urmat de Piticot pană în zona unde se găseşte comoara.

 

Date de intrare

Fişierul de intrare va conţine pe prima linie numarul n, ce reprezintă latura pădurii şi numărul secret (maxim 9 cifre), pe următoarele n linii se găsesc câte n valori reprezentând timpul de parcurgere pentru fiecare zonă a pădurii, valorile fiind separate prin câte un spaţiu.

 

Date de ieşire

Fişierul de ieșire care va conţine pe prima linie timpul minim de parcurgere a pădurii din colţul stânga sus către comoară, iar pe urmatoarele linii traseul parcurs, pe câte o linie fiind trecute coordonatele zonei parcurse.

 

Restricţii

  • 1 ≤ n ≤ 200
  • Timpul maxim de parcurgere pentru o zonă din pădure este 200.
  • Pentru datele de test există întotdeauna soluţie.

 

Exemplu:

  Date  intrare

  5 10001

  2 2 5 8 1

  10 30 7 2 1

  2 20 6 3 1

  3 10 1 17 1

  10 2 1 2 9

  Date iesire

  31

  1 1

  1 2

  2 3

  3 4

  4 4

Explicaţie:

Piticot va ajunge în zona de coordonate 4 4, unde se află numarul secret 17, în format binar 10001.


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 !