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:

#include <bits/stdc++.h>
using namespace std;
ifstream cin("traversare.in");
ofstream cout("traversare.out");
const int di[]={-1 , 0 , 1 , 0};
const int dj[]={0 , 1 , 0 , -1};
int n , m ;
int a[1002][1002], aux[1002][1002];

int ip , jp , is , js;

struct poz{int i , j;};
poz q[1000000];

bool inside(int i , int j){return i>=1 && i<=n && j>=1 && j<=m;}
int lee(int dr)
{
    int st;
    st=1;
    while(st<=dr)
    {
        int i = q[st].i;
        int j = q[st].j;
        if (i == n)break;
        for(int d = 0 ; d < 4 ; d++)
        {
            int inou=i+di[d];
            int jnou=j+dj[d];
            if(inside(inou,jnou) && a[inou][jnou]==0)
            {
                q[++dr].i=inou;
                q[dr].j=jnou;
                a[inou][jnou]=a[i][j]+1;
            }
        }
        st++;
    }
    return a[q[st].i][q[st].j];
}
void renew()
{
    for(int i = 1 ; i <=n ; ++i)
        for(int j = 1 ; j <=m ; ++j)
            a[i][j] = aux[i][j];
}
int main()
{
    cin >> n >> m;
    for(int i = 1 ; i <=n ; ++i)
        for(int j = 1 ; j <=m ; ++j)
        {cin >> a[i][j];
        }


    int dr = 0;
    for (int j = 1; j <= m; j ++)
    {
        if (a[1][j] == 0)
        {
            poz start;
            start.i = 1;
            start.j = j;
            a[1][j] = 1;
            q[++dr] = start;
        }
    }
    cout << lee(dr);
    return 0;
}