Cerința

Se dă o matrice cu n linii și m coloane. Pentru k poziții date, se cere să se determine drumul de lungime minimă care pleacă de la poziția i1 și j1 și trece prin toate cele k poziții (nu contează în ce ordine), ajungând în final în poziția i2 si j2.

Date de intrare

Fișierul de intrare lee1.in conține pe prima linie numerele n și m. Pe următoarele n linii vor fi câte m numere, 0 sau 1, 0 însemnând că se poate trece prin poziția i și j și 1 însemnând că la poziția i și j este un obstacol și nu se poate trece prin poziția respectivă. Pe următoarea linie se vor afla patru numere: i1, j1, i2 si j2 cu semnificația din enunț. Pe următoarea linie se află numărul k, urmat de k perechi de numere i și j după cum reiese și din enunț.

Date de ieșire

Fișierul de ieșire lee1.out va conține pe prima linie numărul C reprezentând numărul minim de poziții din matrice prin care se va trece începând cu i1 și j1, pentru a trece prin toate cele k poziții și terminând în poziția i2 și j2. Pe următoarele linii se vor afișa k + 2 perechi de numere i și j reprezentând ordinea în care sunt parcurse cele k poziții, inclusiv poziția inițială și cea finală. Indicii pozițiilor se separă prin virgulă. Dacă există mai multe trasee de aceeași lungime minimă, atunci se va afișa traseul minim lexicografic (după indicele liniei și cel al coloanei).

Restricții și precizări

• 1 ≤ n, m ≤ 100
• 1 ≤ k ≤ 5
• 1 ≤ i1, i2, ik ≤ n
• 1 ≤ j1, j2, jk ≤ m
• Se garantează că există soluție pentru toate testele

Exemplu

lee1.in

4 5
0 0 0 0 0
1 0 1 1 1
1 0 0 0 1
1 1 0 0 0
1 1 4 4
3
1 5
3 2
3 4

lee1.out

12
1,1
1,5
3,2
3,4
4,4

Explicatie:

Se pleacă din poziția 1,1 și se merge în poziția 1,5 apoi în 3,2 apoi în 3,4 și apoi ajunge la destinație în 4,4.

#include <bits/stdc++.h>

using namespace std;

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

#define INF 1000000001

struct punct{
    int i, j;
}p[7], rez[10];

int n, m, k, a[101][101], b[101][101], P[10], x[10];
int is, js, ifi, jfi;
int dmin = INF;
int l;

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

void sterg(int g[101][101]){
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
            g[i][j] = 0;
}

bool inmat(int i, int j){
    return i <= n && j <= m && i >= 1 && j >= 1;
}

int lee(int si, int sj, int fi, int fj){
    sterg(b);
    queue<punct> Q;
    Q.push({si, sj});
    b[si][sj] = 1;
    while(!Q.empty()){
        punct x = Q.front();
        for(int d = 0; d <= 3; ++d){
            int i = di[d] + x.i;
            int j = dj[d] + x.j;
            if(inmat(i, j) && a[i][j] == 0 && b[i][j] == 0)
            b[i][j] = b[x.i][x.j] + 1, Q.push({i, j});
        }
        Q.pop();
    }
    return b[fi][fj] - 1;
}

void verif(){
    int dist = 0;
    for(int i = 1; i <= k + 1; ++i)
        dist += lee(p[x[i-1]].i, p[x[i-1]].j, p[x[i]].i, p[x[i]].j);
    if(dist < dmin){
        dmin = dist;
        for(int i = 1; i <= k; ++i)
            rez[i] = {p[x[i]].i, p[x[i]].j};
    }
}

void back(int t){
    for(int i = 1; i <= k; ++i)
        if(!P[i]){
            P[i] = 1;
            x[t] = i;
            if(t == k)
                verif();
            else
                back(t + 1);
            P[i] = 0;
        }
}

int main(){
    fin >> n >> m;
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
            fin >> a[i][j];
    fin >> is >> js >> ifi >> jfi;
    fin >> k;
    for(int i = 1; i <= k; ++i)
        fin >> p[i].i >> p[i].j;
    p[0] = {is, js};
    p[k + 1] = {ifi, jfi};
    x[k + 1] = k + 1;
    back(1);
    fout << dmin << '\n';
    fout << is << ',' << js << '\n';
    for(int i = 1; i <= k; ++i)
        fout << rez[i].i << ',' << rez[i].j << '\n';
    fout << ifi << ',' << jfi << '\n';
    return 0;
}