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

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.

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

#include <fstream>
#include <queue>
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(){
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
            b[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();
    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){
        if(lee(p[x[i-1]].i, p[x[i-1]].j, p[x[i]].i, p[x[i]].j) != INF)
            dist += lee(p[x[i-1]].i, p[x[i-1]].j, p[x[i]].i, p[x[i]].j);
        else
            return ;
    }
    if(dist < dmin){
        dmin = dist;
        for(int i = 1; i <= k; ++i)
            rez[i] = {p[x[i]].i, p[x[i]].j};
    }
    else if(dist == dmin){
        bool mm = false;
        for(int i = 1; i <= k; ++i){
            if(rez[i].i > p[x[i]].i){
                mm = true;
                break;
            }
            else if(rez[i].i == p[x[i]].i){
                if(rez[i].j > p[x[i]].j){
                    mm = true;
                    break;
                }
                else if(rez[i].j < p[x[i]].j)
                    break;
            }
            else if(rez[i].i < p[x[i]].i)
                break;
        }
        if(mm)
            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;
}

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 #3283 Lee1

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