Se consideră o matrice cu N linii și N coloane, numerotate de la 1 la N, care memorează doar valori 0 și 1. Se dau de asemenea coordonatele a trei componente din această matrice.

Cerința

Să se determine lungimea minimă a unui drum care pleacă din poziția (1,1), trece obligatoriu prin cele trei componente date (nu contează în ce ordine) și apoi ajunge în poziția (N, N), drum care trece doar prin componente marcate cu 0 și învecinate pe linii și coloane. Un pas din drum constă din deplasarea dintr-un punct (i,j) într-unul din cele patru învecinate pe linie și coloană, adică într-unul din punctele (i-1,j), (i,j-1), (i+1, j), (i,j+1).

Date de intrare

Programul citește de la tastatură numărul N. Pe fiecare din următoarele N linii și N coloane este descrisă matricea binară. Pe ultimele trei linii sunt câte două numere naturale de forma x y ce descriu coordonatele în matrice (linie și coloană) ale celor trei puncte.

Date de ieșire

Programul va afișa pe ecran un singur număr natural, care reprezintă lungimea minimă a drumului care pornește din (1, 1), trece prin cele trei puncte date și ajunge în punctul (N, N).

Restricții și precizări

3 ≤ N ≤ 100
Cele trei puncte sunt distincte, diferite de pozițiile (1,1) și (N,N) și se găsesc la poziții din matrice marcate cu 0. De asemenea, la pozițiile (1,1) și (N,N) se găsește mereu valoarea 0.
Pentru datele de intrare va exista mereu soluție, adică există cel puțin un drum de la (1,1) la (N,N).

Exemplu

Intrare

Ieșire

Explicație

Cele trei puncte sunt situate în coordonatele (3,3), (1,4), (3,1).
Drumul de lungime minimă este:

de la (1,1) la (1,4) (lungime 3)
de la (1,4) la (3,1) (lungime 5)
de la (3,1) la (3,3) (lungime 2)
de la (3,3) la (4,4) (lungime 2)
Lungime totală: 3 + 5 + 2 + 2 = 12.

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

#include<bits/stdc++.h>
using namespace std;

int a[105][105], n;
int d1[105][105];
int d2[105][105];
int d3[105][105];
int dx[] = {0, 0, -1, 1};
int dy[] = {-1, 1, 0, 0};

pair<int, int> A[4];

queue< pair<int, int> > q;

void Init()
{
    int i, j;
    for (i = 1; i <= n; i++)
        for (j = 1; j <= n; j++)
            d1[i][j] = d2[i][j] = d3[i][j] = 1000000;
}

void Bordare()
{
    int i;
    for (i = 0; i <= n + 1; i++)
        a[0][i] = a[i][0] = a[n + 1][i] = a[i][n + 1] = 1;
}

void Lee(int x, int y, int d[105][105])
{
    int i, j, k;
    d[x][y] = 0;
    q.push({x, y});
    while (!q.empty())
    {
        i = q.front().first;
        j = q.front().second;
        q.pop();
        for (k = 0; k < 4; k++)
        {
            x = i + dx[k];
            y = j + dy[k];
            if (a[x][y] == 0 && d[x][y] > d[i][j] + 1)
            {
                d[x][y] = 1 + d[i][j];
                q.push({x, y});
            }
        }
    }
}

void Afisare()
{
    int M = 1000000;
    /// (1,1) - A - B - C - (n,n)
    M = min(M, d1[1][1] + d1[A[2].first][A[2].second] +
            d3[A[2].first][A[2].second] + d3[n][n]);
    /// (1,1) - A - C - B - (n,n)
    M = min(M, d1[1][1] + d1[A[3].first][A[3].second] +
            d2[A[3].first][A[3].second] + d2[n][n]);
    /// (1,1) - B - A - C - (n,n)
    M = min(M, d2[1][1] + d2[A[1].first][A[1].second] +
            d3[A[1].first][A[1].second] + d3[n][n]);
    /// (1,1) - B - C - A - (n,n)
    M = min(M, d2[1][1] + d2[A[3].first][A[3].second] +
            d1[A[3].first][A[3].second] + d1[n][n]);
    /// (1,1) - C - A - B - (n,n)
    M = min(M, d3[1][1] + d3[A[1].first][A[1].second] +
            d2[A[1].first][A[1].second] + d2[n][n]);
    /// (1,1) - C - B - A - (n,n)
    M = min(M, d3[1][1] + d3[A[2].first][A[2].second] +
            d1[A[2].first][A[2].second] + d1[n][n]);
    cout << M;
}

void Citire()
{
    int i, j;
    cin >> n;
    for (i = 1; i <= n; i++)
        for (j = 1; j <= n; j++)
            cin >> a[i][j];
    for (i = 1; i <= 3; i++)
        cin >> A[i].first >> A[i].second;
}

int main()
{
    Citire();
    Bordare();
    Init();
    Lee(A[1].first, A[1].second, d1);
    Lee(A[2].first, A[2].second, d2);
    Lee(A[3].first, A[3].second, d3);
    Afisare();
    return 0 ;
}

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 #3277 Lee

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