Oraşele Nordemos şi Suderim sunt separate de un munte foarte înalt. Inginerul Negrimon a fost desemnat să construiască un drum prin munte care să unească cele două oraşe. Harta care i s-a pus la dispoziţie descrie muntele ca o matrice cu N linii şi M coloane numerotate de la 1 la N, respectiv de la 1 la M . Un drum reprezintă o succesiune de elemente din matrice cu proprietatea că oricare două elemente consecutive sunt alăturate, pe linie sau pe coloană. Un drum uneşte oraşul Nordemos (linia 1) şi oraşul Suderim (linia N). Valorile din matrice reprezintă densităţile rocilor din munte în acele zone. Pentru fiecare drum posibil se poate calcula valoarea dmax, egală cu densitatea maximă a rocilor pe care le traversează. Negrimon trebuie să construiască un drum pentru care valoarea dmax este cea mai mică.

Cerinţa

Ajută-l pe Negrimon să afle cea mai mică dintre densităţile dmax corespunzătoare drumurilor care unesc Nordemos şi Suderim în condiţiile de mai sus.

Date de intrare

Pe prima linie a fişierului drum.in se află valorile N M VMAX, separate prin câte un spaţiu, reprezentând numărul de linii, numărul de coloane, respectiv densitatea maximă posibilă a rocilor. Următoarele VMAX linii, conţin informaţii despre fiecare densitate de la 1 la VMAX. Astfel, linia k+1 din fişier are următoarea structură: nr p1 p2 p3 … pnr unde nr este numărul de poziţii pe care apare densitatea k iar p1 p2 p3 … pnr reprezintă poziţiile din matrice pe care apare aceasta (valorile sunt separate prin câte un spaţiu). Poziţiile din matrice sunt numerotate consecutiv, de la 1 la N*M, în sensul parcurgerii pe linii, începând cu linia 1. Pe fiecare linie elementele se numerotează de la stânga la dreapta.

Date de ieşire

În fişierul drum.out se va afla o singură valoare ce reprezintă densitatea căutată conform cerinţelor de mai sus.

Restricţii

1 ≤ N,M ≤ 500
1 ≤ VMAX ≤ N*M
0 ≤ nr ≤ N*M
Pentru fiecare poziţie din matrice, densitatea se citeşte exact o dată.
Pot fi densităţi care nu apar în matrice (nr=0).

drum.in

5 5 11
2 3 8
1 23
1 19
1 11
5 9 12 13 15 20
3 4 24 25
1 5
4 10 14 17 21
6 1 2 6 16 18 22
1 7
0

drum.out

Explicaţii

Densitatea 1 apare pe două poziţii în matrice: 3 şi 8; densitatea 2 apare doar pe poziţia 23 etc.

Unul dintre drumurile cu proprietatea din enunţ este cel evidenţiat, valoarea dmax pentru acest drum este 8 şi nu există alt drum cu o densitate dmax mai mică.
Densitatea 11 nu apare în matrice deoarece numărul de apariţii este 0.

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

//Autor: Stefan Negrus 
//O(N*M) - 100 puncte

#include <fstream>
#define DMAX 501
#define INFILE "drum.in"
#define OUTFILE "drum.out"

using namespace std ;

ifstream FIN (INFILE) ;
ofstream FOUT (OUTFILE) ;

int mat[DMAX][DMAX] ;
int d1[4]={-1, 0, 1, 0}, d2[4]={0, 1, 0, -1} ;
int N, M, VMAX ;
int CX[DMAX * DMAX + 1], CY[DMAX * DMAX + 1] ;

int Solve() ;
void Read() ;
void Path(int x, int y, int val) ;
void GetXY(int& x, int& y, int pos) ;

int main()
{
    int i, ok1 ;
    Read() ;
    for (i = 1; i <= VMAX; ++ i)
    {
        ok1 = Solve() ;
        if (ok1)
        {
            FOUT << i << '\n' ;
            return 0 ;
        }
    }

    FIN.close() ;
    FOUT.close() ;
    return 0 ;
}

void Read()
{
    FIN >> N >> M >> VMAX ;
}

void GetXY(int& x, int& y, int pos)
{
    x = pos / M ;
    if (pos % M)
    {
        ++ x ;
    }
    y = pos % M ;
    if (!y)
    {
        y = M ;
    }
}

int Solve()
{
    int nr, i, pos, x, y, k, ok1, ok2 ;
    FIN >> nr ;
    for (i = 1; i <= nr; ++i)
    {
        FIN >> pos ;
        GetXY(x, y, pos) ;
        ok1 = ok2 = 0 ;

        mat[x][y] = 3 ;

        for (k = 0; k < 4; ++k)
        {
            if (mat[x+d1[k]][y+d2[k]] == 1)
            {
                ok1 = 1 ;
                mat[x][y] = 1 ;
            }
            if (mat[x+d1[k]][y+d2[k]] == 2)
            {
                ok2 = 2 ;
                mat[x][y] = 2 ;
            }
        }

        if (x == 1)
        {
            mat[x][y] = 1 ;
            ok1 = 1 ;
        }

        if (x == N)
        {
            mat[x][y] = 2 ;
            ok2 = 1 ;
        }

        if (ok1 && ok2)
        {
            return 1 ;
        }

        if (mat[x][y] != 3)
        {
            Path(x, y, mat[x][y]) ;
        }
    }
    return 0 ;
}

void Path(int x, int y, int val)
{
    int k ;
    int st, en ;
    st = en = 1 ;
    CX[st] = x ;
    CY[st] = y ;
    while(st <= en)
    {
        x = CX[st] ;
        y = CY[st] ;
        ++st ;
        mat[x][y] = val ;
        for (k = 0; k < 4; ++k)
        {
            if (mat[x+d1[k]][y+d2[k]] == 3)
            {
                mat[x+d1[k]][y+d2[k]] = val ;
                ++en ;
                CX[en] = x + d1[k] ;
                CY[en] = y + d2[k] ;
            }
        }
    }
}

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 #151 drum

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