Cerința
Se consideră harta unei suprafețe deșertice, dată sub forma unei matrice cu n linii și m coloane, formată din n*m zone. Fiecare zonă poate fi accesibilă sau inaccesibilă. Dintr-o zonă accesibilă se poate trece în altă zonă accesibilă învecinată cu prima pe linie sau pe coloană.
Un călător dorește să traverseze deșertul de la nord (prima linie) la sud(ultima linie). Pentru aceasta el poate sa aleagă oricare zonă accesibilă de pe prima line și dorește să ajungă pe ultima linie cu număr minim de pași.
Date de intrare
Fișierul de intrare traversare.in conține pe prima linie numerele n m. Următoarele n linii conțin câte m valori 0 sau 1, separate prin câte un spațiu. Valoarea 0 reprezintă o zonă accesibilă, iar valoarea 1 reprezintă o zonă inaccesibilă.
Date de ieșire
Fișierul de ieșire traversare.out va conține pe prima linie numărul C, reprezentând numărul minim de pași necesari pentru traversare.
Restricții și precizări
1 ≤ n , m ≤ 1000- în traversarea deșertului un pas este trecerea dintr-o zonă accesibilă în altă zonă accesibilă învecinată cu prima
- la determinarea numărului de pași se numără și primul pas (intrarea în matrice)
- pentru toate datele de test este posibilă traversarea deșertului
Exemplu
traversare.in
6 9 1 1 0 0 1 1 1 0 0 0 0 1 0 1 0 1 1 0 1 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 1 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 1 0
traversare.out
8
Explicație
O traversare cu 8 pași a deșertului este următoarea:
| 1 | 1 | 0 | 0 | 1 | 1 | 1 | 0 | 0 |
| 0 | 0 | 1 | 0 | 1 | 0 | 1 | 1 | 0 |
| 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 |
| 1 | 0 | 1 | 1 | 0 | 1 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 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 Traversare:
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("traversare.in");
ofstream fout("traversare.out");
int n , m, nrI, nrP;
int a[1002][1002];
short x[1000005], y[1000005];
const int dx[]={0 , 0 , 1 , -1}, dy[]={1 , -1 , 0 , 0};
int main(){
fin >> n >> m;
for(int i = 1 ; i <= n ; i ++)
for(int j = 1 ; j <= m ; j ++)
fin >> a[i][j];
//facem obstacolele -1
for(int i = 1 ; i <= n ; i ++)
for(int j = 1 ; j <= m ; j ++)
a[i][j] = - a[i][j];
int st = 1 , dr = 0;
for(int j =1 ; j <= m ; j ++)
if(a[1][j] == 0)
{
dr ++;
x[dr] = 1 , y[dr] = j;
a[1][j] = 1;
}
while(st <= dr)
{
int i = x[st] , j = y[st];
for(int k = 0 ; k < 4 ; k ++)
{
int ii = i + dx[k] , jj = j + dy[k];
if(ii > 0 && ii <= n && jj > 0 && jj <= m && a[ii][jj] == 0)
{
dr ++;
x[dr] = ii, y[dr] = jj;
a[ii][jj] = a[i][j] + 1;
}
}
st ++;
}
int mmin = 1000005;
for(int j = 1 ; j <= m ; j ++)
if(a[n][j] > 0)
if(a[n][j] < mmin)
mmin = a[n][j];
fout << mmin << "
";
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 
.
Rezolvarea problemei #883 Traversare
Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #883 Traversare 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!