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

4
0 0 0 0
1 0 1 1
0 0 0 1
1 0 0 0
3 3
1 4
3 1

Ieșire

12

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.

#include <bits/stdc++.h>



using namespace std;

#define MAX 1000001
#define inf 10000000

bool a[101][101];
int d[101][101][8];

int di[] = {1, 0, -1, 0};
int dj[] = {0, 1, 0, -1};
int n;

pair<int, int> puncte[3];

void lee(pair<int, int> source)
{
    queue< pair<int, int> > Q;
    Q.push(source);
    d[1][1][0] = 0;
    pair<int, int> node;
    int ok = 0;
    while (!Q.empty())
    {
        node = Q.front();

        Q.pop();

        ok = 0;
        for (int i = 0; i < 3; ++ i)
            if (node == puncte[i])
                ok = (1 << i);

        for (int dir = 0, inou, jnou; dir < 4; ++ dir)
        {
            inou = node.first + di[dir];
            jnou = node.second + dj[dir];
            if (a[inou][jnou] == 1 || inou < 1 || jnou < 1 || inou > n || jnou > n)continue;

            for (int i = 0; i < 8; ++ i)
                if (d[inou][jnou][i | ok] > d[node.first][node.second][i] + 1)
                {
                    d[inou][jnou][i | ok] = d[node.first][node.second][i] + 1;
                    Q.push({inou, jnou});
                }
        }
    }
}
int main()
{
    cin >> n;
    for (int i = 1; i <= n; ++ i)
        for (int j = 1; j <= n; ++ j)
        {
            cin >> a[i][j];
            for (int k = 0; k < 8; ++ k)
                d[i][j][k] = inf;
        }
    for (int i = 0; i < 3; ++ i)
        cin >> puncte[i].first >> puncte[i].second;
    lee({1, 1});
    cout << d[n][n][7];
    return 0;
}