Cerința

Zoli și D’Umbră s-au pierdut într-un labirint cu n x n camere dispuse pe cate n linii și n coloane. D’umbră se află în camera (1, 1), iar Zoli se află în camera (n, n). Aceștia vor trebui să parcurgă labirintul pentru a se regăsi. Dacă unul dintre ei se aflâ în camera (i, j), acesta se poate deplasa spre una din camerele aflate la pozițiile (i + 1, j), (i, j + 1), (i - 1, j) sau (i, j - 1), fără a părăsi labirintul.

Camerele nu pot fi accesate ușor. La fiecare cameră se află câte o ușă având o rezistență R care poate fi spartă cu un baros cu o putere P ≥ R. Unul dintre cei doi (nu contează care) va avea acces la un arsenal de barosuri cu puteri între 0 și 100.000.

Determinați puterea minimă pe care o poate avea barosul ce trebuie folosit astfel încât Zoli și D’Umbră să se poată întâlni.

Date de intrare

Fișierul de intrare labirint.in conține pe prima linie numărul n, iar pe următoarele n linii n numere, al j -lea număr de pe linia i + 1 reprezintă rezistența ușii de la camera aflată în (i, j).

Date de ieșire

Fișierul de ieșire labirint.out va conține pe prima linie numărul Pmin, reprezentând puterea minimă pe care o poate avea un baros folosit pentru a sparge anumite uși și a conecta camerele (1, 1) și (n, n).

Restricții și precizări

1 ≤ n ≤ 1.000
0 ≤ rezistența unei uși ≤ 100.000
pentru 50% din punctaj, Pmin ≤ 600 și n ≤ 500

Exemplu

labirint.in

labirint.out

Explicație

(1, 1) -> (2, 1) -> (3, 1) -> (3, 2) -> (3, 3) -> (4, 3) -> (4, 4)
Se evită camerele cu rezistență mai mare decât 2.

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 Labirint:

#include <fstream>
#include <queue>
using namespace std;

ifstream fin ("labirint.in");
ofstream fout ("labirint.out");

const int N = 1005;

const int dx[] = {-1, 0, 1, 0},
          dy[] = {0, 1, 0, -1};

int a[N][N], v[N][N], n, sol, step = 1 << 16;
queue <pair <int, int> > Q;

int lee(int k) {
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            v[i][j] = 0;
    if (a[1][1] <= k)
        Q.push(make_pair (1, 1));
    else
        return 0;
    while (Q.size() && !v[n][n]) {
        int x = Q.front().first;
        int y = Q.front().second;
        Q.pop();
        for (int crt = 0; crt < 4; ++crt) {
            int xx = x + dx[crt];
            int yy = y + dy[crt];
            if (!v[xx][yy] && a[xx][yy] <= k) {
                v[xx][yy] = 1;
                Q.push(make_pair (xx, yy));
            }
        }
    }
    while (Q.size())
        Q.pop();
    return v[n][n];
}

int main() {
    fin >> n;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            fin >> a[i][j];
    for (int i = 0; i <= n + 1; ++i)
        for (int j = 0; j <= n + 1; ++j)
            v[i][j] = 1;
    for (; step; step >>= 1)
        if (!lee(sol + step))
            sol += step;
    fout << sol + 1;
}

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 #1238 Labirint

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1238 Labirint 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!

Rezolvare completă PbInfo #1238 Labirint