# PBinfo #1998 – Rover – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: Darius

## Enunț

NASA plănuiește o nouă misiune Rover pe Marte în anul 2020. Principalul obiectiv al acestei misiuni este de a determina, cu ajutorul unui nou Rover, dacă a existat în trecut viață pe Marte. Până când va fi lansată misiunea, Roverul este supus la tot felul de teste în laboratoarele NASA. Într-unul din teste, Roverul trebuie să parcurgă o suprafață de forma unui caroiaj cu N linii și N coloane. Acesta pornește din zona de coordonate (1,1) și trebuie să ajungă în zona de coordonate (N,N), la fiecare pas putându-se deplasa din zona în care se află într-una din zonele învecinate la nord, sud, est sau vest. Pentru fiecare zonă de coordonate (i,j) se cunoaște A[i,j], stabilitatea terenului din acea zonă. Știind că Roverul are o greutate G, o zonă cu stabilitatea terenului cel puțin egală cu G se consideră o zonă sigură pentru deplasarea Roverului, iar o zonă cu stabilitatea terenului mai mică decât G se consideră o zonă periculoasă pentru Rover.

Cerințe
1. Determinați numărul minim posibil de zone periculoase pe care le traversează Roverul pentru a ajunge din zona (1,1) în zona (N,N).
2. Determinați greutatea maximă pe care o poate avea un Rover care să ajungă din zona (1,1) în zona (N,N), fără a traversa nicio zonă periculoasă pentru el.

Date de intrare
Fișierul de intrare rover.in conține pe prima linie numărul natural V a cărui valoare poate fi doar 1 sau 2. Dacă V este 1, pe a doua linie a fișierului de intrare se găsesc două numere naturale N și G cu semnificația din enunț, iar dacă V este 2, pe a doua linie a fișierului de intrare se află doar numărul N.

Pe următoarele N linii se află câte N numere A[i,j], reprezentând stabilitatea terenului din zona (i,j).

Date de ieșire
Fișierul de ieșire este rover.out.

Dacă valoarea lui V este 1, atunci fișierul de ieșire va conține pe prima linie un număr natural reprezentând numărul minim de zone periculoase pe care trebuie să le traverseze Roverul de greutate G.

Dacă valoarea lui V este 2, atunci fișierul de ieșire va conține pe prima linie un număr natural reprezentând greutatea maximă a unui Rover care poate ajunge din zona (1,1) în zona (N,N) fără a traversa zone periculoase pentru el.

Restricții și precizări

Pentru 50% din teste V = 1, pentru 50 % din teste V = 2.
1 ≤ N ≤ 500
1 ≤ G ≤ 5000
1 ≤ A[i,j] ≤ 10000
Zonele de coordonate (1,1) și (N,N) nu sunt zone periculoase pentru Rover.
Roverul nu va trece de mai multe ori prin aceeași zonă.

Exemplul 1
rover.in

1
5 5
5 1 3 4 7
5 2 1 8 5
2 9 5 3 3
4 1 1 1 9
5 1 6 1 8
rover.out

3
Explicație
Numărul minim de zone periculoase traversate de la poziția (1,1) până la poziția (5,5) este 3. Un traseu posibil este:



 5 
 1 
 3 
 4 
 7 


 5 
 2 
 1 
 8 
 5 


 2 
 9 
 5 
 3 
 3 


 4 
 1 
 1 
 1 
 9 


 5 
 1 
 6 
 1 
 8 


Exemplul 2
rover.in

2
5
5 1 3 4 7
5 2 1 8 5
2 9 5 3 3
4 1 1 1 9
5 1 6 1 8
rover.out

2
Explicație
Greutatea maximă a unui Rover care poate ajunge din zona (1,1) în zona (5,5) fără a trece prin zone periculoase pentru el este 2. Un traseu posibil este:



 5 
 1 
 3 
 4 
 7 


 5 
 2 
 1 
 8 
 5 


 2 
 9 
 5 
 3 
 3 


 4 
 1 
 1 
 1 
 9 


 5 
 1 
 6 
 1 
 8

## Cod sursă C++

```cpp
// prof. Mircea Lupse-Turpan - Liceul Teoretic Grigore Moisil Timisoara - 100 puncte
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("rover.in");
ofstream fout("rover.out");
struct Cell
{
    int x, y;
    Cell * next;
};
const int NMax = 505;
const int oo = 10000;
int A[NMax][NMax],DP[NMax][NMax];
int V,N,G;
int dx[] = {-1,0,1,0}, dy[] = {0,1,0,-1};
Cell * First, * Last;
void Add_Front(int V1, int V2)
{
    Cell * p = new Cell;
    p -> x = V1;
    p -> y = V2;
    p -> next = First;
    if(!First)
        Last = p;
    First = p;
}
void Add_Back(int V1, int V2)
{
    Cell * p = new Cell;
    p -> x = V1;
    p -> y = V2;
    p -> next = NULL;
    if(!First)
        First = p;
    else
        Last -> next = p;
    Last = p;
}
void Delete_Front()
{
    Cell * p;
    p = First;
    First = First -> next;
    delete p;
    if(!First) Last = NULL;
}
bool isEmpty()
{
    return (First == NULL);
}
void Read()
{
    fin >> V >> N;
    if(V == 1) fin >> G;
    for(int i = 1; i <= N; ++i)
        for(int j = 1; j <= N; ++j)
            fin >> A[i][j];
}
inline bool Inside(int x, int y)
{
    return ( (x >= 1) && (x <= N) && (y >= 1) && (y <= N) );
}
void Solve1()
{
    memset(DP,-1,sizeof(DP));
    Add_Back(1,1);
    DP[1][1] = 0;
    while(!isEmpty())
    {
        int X = First -> x, Y = First -> y;
        Delete_Front();
        for(int k = 0; k < 4; k++)
        {
            int NewX = X + dx[k], NewY = Y + dy[k];
            if(Inside(NewX,NewY) && DP[NewX][NewY] == -1)
            {
                if(A[NewX][NewY] < G)
                {
                    DP[NewX][NewY] = DP[X][Y] + 1;
                    Add_Back(NewX,NewY);
                }
                else
                {
                    DP[NewX][NewY] = DP[X][Y];
                    Add_Front(NewX,NewY);
                }
            }
        }
    }
    fout << DP[N][N] << "\n";
}
bool Lee(int Value)
{
    memset(DP,-1,sizeof(DP));
    Add_Back(1,1);
    DP[1][1] = 0;
    while(!isEmpty())
    {
        int X = First -> x, Y = First -> y;
        Delete_Front();
        for(int k = 0; k < 4; k++)
        {
            int NewX = X + dx[k], NewY = Y + dy[k];
            if(Inside(NewX,NewY) && DP[NewX][NewY] == -1)
            {
                if(A[NewX][NewY] >= Value)
                {
                    DP[NewX][NewY] = DP[X][Y] + 1;
                    Add_Back(NewX,NewY);
                }
            }
        }
    }
    return (DP[N][N] != -1);
}
void Solve2()
{
    int Left = 1, Right = oo, Sol = -1;
    while(Left <= Right)
    {
        int Mid = (Left + Right) / 2;
        if(Lee(Mid))
        {
            Sol = Mid;
            Left = Mid + 1;
        }
        else
            Right = Mid - 1;
    }
    fout << Sol << "\n";
}
int main()
{
    Read();
    if(V == 1)
        Solve1();
    else
        Solve2();
    return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/1998)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/1998/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-1998/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)