Rezolvare completă PbInfo #1998 Rover

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

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Rover:

// 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] << "
";
}

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 << "
";
}


int main()
{
    Read();
    if(V == 1)
        Solve1();
    else
        Solve2();
    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email.

Rezolvarea problemei #1998 Rover

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1998 Rover de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!