Fişierul intrare/ieşire:robot2.in, robot2.outSursăONI 2011 - Baraj
AutorStelian CiureaAdăugată desavimSerban Andrei Stan savim
Timp execuţie pe test0.8 secLimită de memorie131072 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Robot2

Un labirint este dat sub forma unui tablou pătratic cu n × n elemente 0 şi 1, având semnificaţia: 0 reprezintă poziţie liberă, iar 1 poziţie ocupată. Un robot aflat în labirint, pe linia L1 şi coloana C1, trebuie să ajungă într-o poziţie finală de pe linia L2 şi coloana C2. Robotul se poate deplasa numai pe direcţiile orizontală şi verticală.

Cerinţe

Scrieţi un program care determină:

1) Numărul minim de schimbări de direcţie pentru ca robotul să se deplaseze din poziţia (L1, C1) în poziţia (L2, C2).

2) Numărul minim de schimbări de direcţie pentru ca robotul să se deplaseze din poziţia (L1, C1) în poziţia (L2, C2), în situaţia în care putem transforma o singură poziţie ocupată într-o poziţie liberă.

3) Numărul de obstacole cu proprietatea că oricare dintre ele ar fi eliminate, se obţine numărul minim de schimbări de direcţie de la cerinţa 2).

Date de intrare

Pe prima linie a fişierului robot2.in se găseşte numărul natural n. Pe următoarele n linii se află câte n valori 0 sau 1 separate prin câte un spaţiu, reprezentând elementele labirintului. Pe linia n+2, sunt numerele L1 C1 L2 C2.

Date de ieşire

Prima linie a fişierului robot2.out conţine trei numere naturale, separate printr-un spaţiu, reprezentând răspunsurile la cele trei cerinţe.

Restricţii

  • 1 ≤ n ≤ 1000
  • Se garantează că robotul poate ajunge din poziţia (L1, C1) în poziţia (L2, C2).
  • Pentru 30% din cazuri n ≤ 100.
  • Numerotarea liniilor şi a coloanelor începe de la 1.
  • Pentru rezolvarea corectă a primei cerinţe se acordă 20% din punctajul unui test. Pentru rezolvarea corectă a primelor două cerinţe se acordă 50% din punctajul unui test. Pentru rezolvarea corectă a tuturor celor trei cerinţe se acordă 100% din punctaj.

Exemplu

robot2.inrobot2.out
5
0 1 1 0 0
0 0 0 1 0
1 0 1 1 0
0 0 0 1 0
0 0 0 0 0
1 1 1 5
4 2 2

Explicaţie

Obstacolele care pot fi eliminate sunt cele de la 2,4 si 3,1.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content