# PBinfo #3717 – Labirint5 – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: andrei

## Enunț

Un labirint este descris ca fiind o matrice binară cu N linii și M coloane, cu semnificația că 0 reprezintă o poziție liberă, iar 1 reprezintă o poziție în care se află un zid. Un drum în labirint este un traseu în matrice care începe cu poziția (1, 1) și ajunge în poziția (N, M) prin deplasare doar pe poziții care au valoarea 0 și sunt vecine cu poziția curentă, pe una din cele patru direcții: sus, jos, stânga, dreapta. Lungimea unui drum este egală cu numărul de poziții vizitate. 

Notăm cu d0 lungimea drumului minim de la poziția (1, 1) la poziția (N,M). Fie d(i, j) lungimea drumului minim de la poziția (1, 1) la poziția (N, M), dacă poziției (i, j) i se atribuie valoarea 0. Observăm că dacă poziția (i, j) conține inițial un 0, atunci d0 = d(i, j).

Cerința
Pentru fiecare poziție (i, j) să se verifice dacă d(i, j) < d0.

Date de intrare
Pe prima linie a fișierului de intrare labirint.in se află două numere naturale N și M, dimensiunile matricei binare ce descrie labirintul, apoi pe următoarele N linii se vor afla câte M valori binare, ce reprezintă elementele matricei care descrie labirintul, neseparate prin spații.

Date de ieșire
În fișierul de ieșire labirint.out se vor scrie N linii, iar pe fiecare linie se vor scrie M cifre, neseparate prin spații. Cifra a j-a de pe linia a i-a este 1 dacă și numai dacă d(i, j) < d0, altfel este 0.

Restricții și precizări

1 ≤ N ≤ 1000
1 ≤ M ≤ 1000
Pe pozițiile (1, 1) și (N, M) se vor afla valori 0.
Se garantează că există un drum în matricea inițială între pozițiile (1, 1) și (N, M).
Pentru 10 puncte, 1 ≤ N ≤ 50, 1 ≤ M ≤ 50, d0 = N + M - 1.
Pentru alte 30 de puncte, 1 ≤ N ≤ 50, 1 ≤ M ≤ 50
Pentru alte 60 de puncte, fără alte restricții

Exemplu:
labirint.in

5 6
010001
000101
011001
010010
001000
labirint.out

010000
000100
001001
010010
001000
Explicație
Sunt 7 poziții cu valoarea 1 în labirint care dacă se înlocuiesc cu 0 determină obținerea unui drum de lungime mai mică decât d0 = 14. De exemplu, dacă am înlocui valoarea din (1, 2) cu 0, am obține un drum de lungime d(1, 2) = 12.

## Cod sursă C++

```cpp
#include <fstream>
#define DIM 1002
#define BLOCK 1000001
using namespace std;
int a[DIM][DIM], b[DIM][DIM], c[2][DIM*DIM];
char sol[DIM][DIM];
int n, m, i, j, poz, neg, d0;
pair<int, int> P[5], M[5];
int di[] = {-1, 1, 0, 0};
int dj[] = { 0, 0,-1, 1};
char s[DIM];
void lee(int is, int js, int a[DIM][DIM], int marc) {
    int p = 1, u = 1;
    c[0][1] = is;
    c[1][1] = js;
    a[is][js] = 1*marc;
    while (p <= u) {
        int ic = c[0][p];
        int jc = c[1][p];
        for (int d = 0; d<=3; d++) {
            int iv = ic + di[d];
            int jv = jc + dj[d];
            if (iv >= 1 && iv <= n && jv >= 1 && jv <= m && a[iv][jv] == 0) {
                u++;
                c[0][u] = iv;
                c[1][u] = jv;
                a[iv][jv] = a[ic][jc] + (1*marc);
            }
        }
        p++;
    }
}
int main () {
    ifstream fin ("labirint.in");
    ofstream fout("labirint.out");
    fin>>n>>m;
    for (i=1;i<=n;i++) {
        fin>>s+1;
        for (j=1;j<=m;j++)
            a[i][j] = b[i][j] = (s[j] == '0' ? 0 : BLOCK);
    }
    lee(1, 1, a, 1);
    d0 = a[n][m]-1;
    lee(n, m, b, -1);
    for (i=1;i<=n;i++) {
        for (j=1;j<=m;j++)
            if (a[i][j]!=BLOCK)
                sol[i][j] = '0';
            else {
                poz = 0;
                neg = 0;
                for (int d = 0; d <= 3; d++) {
                    int iv = i+di[d];
                    int jv = j+dj[d];
                    if (iv >= 1 && iv <= n && jv >= 1 && jv <= m) {
                        if (a[iv][jv] > 0)
                            P[++poz] = {iv, jv};
                        if (b[iv][jv] < 0)
                            M[++neg] = {iv, jv};
                    }
                }
                if (poz == 0 || neg == 0) {
                    sol[i][j] = '0';
                } else {
                    int rez = 0;
                    for (int ii=1;ii<=poz;ii++)
                        for (int jj=1;jj<=neg;jj++)
                            if (P[ii] != M[jj])
                                if (a[ P[ii].first ][ P[ii].second ] - 1 - b[ M[jj].first ][ M[jj].second ] + 1 < d0) {
                                    rez = 1;
                                    break;
                                }
                    sol[i][j] = '0' + rez;
                }
            }
    }
    for (i=1;i<=n;i++)
        fout<<sol[i]+1<<"\n";
	fout.close();
    return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/3717)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/3717/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-3717/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)