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).
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 testeV = 2. 1 ≤ N ≤ 5001 ≤ G ≤ 50001 ≤ 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 |
#include <bits/stdc++.h>
using namespace std;
ifstream cin("rover.in");
ofstream cout("rover.out");
const int di[] = {-1 , 0 , 1 , 0};
const int dj[] = { 0 , -1 , 0 , 1};
struct poz
{
int i , j;
};
int a[505][505] , b[505][505] , n , cer , g;
queue <poz> Q;
deque <poz> D;
bool inside(int i , int j)
{
return i >= 1 && i <= n && j >= 1 && j <= n;
}
void lee1()
{
poz p;
p.i = 1 , p.j = 1;
D.push_back(p);
b[1][1] = 1;
while( ! D.empty())
{
p = D.front();
D.pop_front();
for(int i = 0 ; i < 4 ; i ++)
{
int inou = p.i + di[i];
int jnou = p.j + dj[i];
if(inside(inou , jnou) && b[inou][jnou] == 0)
{
if(a[inou][jnou] < g)
{
b[inou][jnou] = b[p.i][p.j] + 1;
poz qa;
qa.i = inou , qa.j = jnou;
D.push_back(qa);
}
else
{
b[inou][jnou] = b[p.i][p.j];
poz qa;
qa.i = inou , qa.j = jnou;
D.push_front(qa);
}
}
}
}
}
int lee2(int g)
{
int b[505][505] = {0};
poz p;
p.i = 1 , p.j = 1;
Q.push(p);
b[1][1] = 1;
while( ! Q.empty())
{
p = Q.front();
for(int i = 0 ; i < 4 ; i ++)
{
int inou = p.i + di[i];
int jnou = p.j + dj[i];
if(inside(inou , jnou) && b[inou][jnou] == 0 && a[inou][jnou] >= g)
{
b[inou][jnou] = b[p.i][p.j] + 1;
poz qa;
qa.i = inou , qa.j = jnou;
Q.push(qa);
}
}
Q.pop();
}
return b[n][n] != 0;
}
int main()
{
cin >> cer;
if(cer == 1)
{
cin >> n >> g;
for(int i = 1 ; i <= n ; i++)
for(int j = 1 ; j <= n ; j++)
cin >> a[i][j];
lee1();
cout << b[n][n] - 1;
}
else
{
cin >> n;
for(int i = 1 ; i <= n ; i++)
for(int j = 1 ; j <= n ; j++)
cin >> a[i][j];
int st = 1 , dr = 10000;
while(st <= dr)
{
int m = (st + dr) / 2;
if(lee2(m))st = m + 1;
else dr = m - 1;
}
cout << dr ;
}
}
