Problema Rover – OJI 2017, Clasa a 10-a

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