| Fişierul intrare/ieşire: | robot2.in, robot2.out | Sursă | ONI 2011 - Baraj |
| Autor | Stelian Ciurea | Adăugată de |  Serban Andrei Stan •savim |
| Timp execuţie pe test | 0.4 sec | Limită de memorie | 131072 kbytes |
| Scorul tău | N/A | Dificultate | N/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.in | robot2.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.
