Problema Rover – OJI 2017, Clasa a 10-a

Problema Rover – OJI 2017, Clasa a 10-a

Rezumat

Avem un rover care se poate deplasa (cu o celulă în nord, sud, est sau vest) într-o matrice pătratică cu nn linii și nn coloane. Fiecare celulă (zonă) a matricei are o stabilitate reprezentată printr-un număr natural, iar rover-ul are greutatea gg O zonă cu stabilitatea mai mică decât gg este considerată o zonă periculoasă pentru rover.

La prima cerință trebuie să determinăm numărul minim de zone periculoase pe care trebuie să le traverseze rover-ul pentru a ajunge de la zona (1,1)(1, 1) la (n,n)(n, n) La a doua cerință se cere greutatea maximă pe care o poate avea rover-ul pentru a putea ajunge din (1,1)(1, 1) în (n,n)(n, n) fără a traversa nicio zonă periculoasă.

Soluție: Cerința 1

Pentru prima cerință putem defini costul unei celule drept numărul minim de zone periculoase pe care rover-ul trebuie să le parcurgă pentru a ajunge la ea. Se observă ușor că atunci când trecem din celula AA în celula BB avem relația de recurență cost(B)=cost(A)+zonaSigura(B)\mathrm{cost}(B) = \mathrm{cost}(A) + \mathrm{zonaSigura}(B) Evident, zonaSigura(B)\mathrm{zonaSigura}(B) este 11 dacă BB este o zonă sigură, și 00 dacă nu. Această recurență ne indică faptul că putem aplica algoritmul lui Lee cu costuri. Adică, în loc să calculăm o distanță minimă, calculăm un cost minim, iar pentru a obține de fiecare dată un cost minim pentru celula curentă, ne vom expanda mai întâi din zonele sigure, iar abia apoi din cele periculoase.

Pentru a respecta această ordine a vizitării zonelor, putem folosi un deque în loc de coadă. În față adăugăm zone sigure, iar în spate zone periculoase. Asta ne garantează că întotdeauna zonele din deque vor fi ordonate descrescător în funcție de costul lor, și deci la fiecare pas continuăm cu cea mai sigură :smile: Pentru a înțelege mai bine, puteți urmări mai jos cum arată deque-ul după fiecare dintre primii șase pași, pentru exemplul din enunțul problemei. Am folosit triplete de forma (a,b,c)(a, b, c) cu semnificația „zona de coordonate (a,b)(a, b) ce are costul cc

(1, 1, 0)
(1, 2, 1) (2, 1, 0)
(2, 2, 1) (3, 1, 1) (1, 2, 1)
(1, 3, 2) (2, 2, 1) (3, 1, 1)
(4, 1, 2) (1, 3, 2) (2, 2, 1) (3, 2, 1)
(4, 2, 2) (4, 1, 2) (1, 3, 2) (2, 2, 1) (3, 3, 1)

Soluție: Cerința 2

Pentru a doua cerință putem folosi tehnica căutării binare pe rezultat. La fiecare pas testăm dacă mijlocul intervalului curent reprezintă o greutate pentru care se poate ajunge din zona (1,1)(1, 1) în zona (n,n)(n, n) Pentru verificare putem folosi atât algoritmul lui Lee, cât și un algoritm de fill. Eu am ales fill recursiv pentru că e mai scurt și oricum nu avem nevoie de lungimea drumului minim. Apoi, dacă greutatea este bună, continuăm căutarea binară în dreapta, în vederea găsirii unei greutăți mai mari. Dacă greutatea nu este bună, înseamnă că este prea mare, așa că vom căuta în stânga una mai mică.

Sursă C++

Problema Rover
#include <deque>
#include <fstream>
#define DMAX 510
std::ifstream fin("rover.in");
std::ofstream fout("rover.out");
// struct pentru celule:
struct Cell {
int lin;
int col;
};
// Vectorii de deplasare:
const int dL[] = {-1, 0, 0, 1};
const int dC[] = { 0, -1, 1, 0};
// Datele problemei:
int c, n, g;
int mat[DMAX][DMAX];
// Pentru cerința 1:
int dp[DMAX][DMAX];
std::deque dq;
// Pentru cerința 2:
int sol;
bool aux[DMAX][DMAX];
/// Funcția ce face Lee cu deque
void leeDeque() {
Cell cell, nghb;
dq.push_front({1, 1}); // Introducem în deque prima celulă.
// dp[i][j] = numărul minim de zone periculoase pe care
// le traversează rover-ul pentru a ajunge în celula (i, j)
// Marcăm toate celulele drept nevizitate:
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
dp[i][j] = -1;
dp[1][1] = 0;
while (!dq.empty()) {
// Scoatem din deque celula cu costul minim:
cell = dq.front();
dq.pop_front();
// Parcurgem vecinii acestei celule:
for (int i = 0; i < 4; i++) {
nghb.lin = cell.lin + dL[i];
nghb.col = cell.col + dC[i];
// Celula nu e vizitată...
if (dp[nghb.lin][nghb.col] == -1) {
// Dacă celula e sigură, o punem în față:
if (mat[nghb.lin][nghb.col] >= g) {
dp[nghb.lin][nghb.col] = dp[cell.lin][cell.col];
dq.push_front(nghb);
}
else { // dacă nu, în spate:
dp[nghb.lin][nghb.col] = dp[cell.lin][cell.col] + 1;
dq.push_back(nghb);
}
}
}
}
}
/// Funcția recursivă de fill
void fill(int i, int j, int g) {
// Ne expandăm doar în zonele sigure:
if (!aux[i][j] && mat[i][j] >= g) {
aux[i][j] = true;
fill(i - 1, j , g);
fill(i + 1, j , g);
fill(i , j - 1, g);
fill(i , j + 1, g);
}
}
/// Funcția care testează dacă greutatea g e fezabilă
bool fillMat(int g) {
// Bordăm matricea:
for (int i = 0; i <= n + 1; i++)
aux[i][0] = aux[i][n + 1] =
aux[0][i] = aux[n + 1][i] = true;
// Marcăm celulele ca nevizitate:
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
aux[i][j] = false;
fill(1, 1, g); // Începem fill-ul.
return aux[n][n]; // Returnăm dacă s-a ajuns în (n, n).
}
int main() {
fin >> c >> n;
if (c == 1)
fin >> g;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
fin >> mat[i][j];
if (c == 1) {
leeDeque();
fout << dp[n][n] << '\n';
}
else {
// Căutare binară pe greutatea maximă:
int md, lo = 0, hi = 10001;
while (hi - lo > 1) {
md = (lo + hi) / 2;
if (fillMat(md)) {
lo = md;
sol = md > sol ? md : sol;
}
else
hi = md;
}
fout << sol << '\n';
}
return 0;
}

Dacă ai vreo nedumerire cu privire la problema Rover, lasă un comentariu și te voi ajuta :smile:

Mulțumesc că ai citit acest articol.
Dacă vrei să susții blogul, poți cumpăra un abonament de 2$.

patreon

Lasă un comentariu!

0 comentarii