Cod sursa(job #1837404)

Utilizator alex2704Pirvuceanu Alexandru alex2704 Data 29 decembrie 2016 17:22:38
Problema BFS - Parcurgere in latime Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.25 kb
#include<fstream>
#include<iostream>
using namespace std;
ifstream f("lee.in");
ofstream g("lee.out");
int t[1001][1001],a[1001][1001],c,pas,is,js,id,jd,x,y,xx,yy,n,m,inf, drumx[1001],drumy[1001],k;

const int dx[]= {-1,-1,0,+1,+1,+1,0,-1};
const int dy[]= {0,+1,+1,+1,0,-1,-1,-1};

int main ()
{  int i,j,k,l;
    f>>n>>m;
    f>>is>>js>>id>>jd;
    for(i=1; i<=n; i++)
        for(j=1; j<=m; j++)
            f>>t[i][j];
    inf=n*m+1;
    for(i=1; i<=n; i++)
        for(j=1; j<=m; j++)
            a[i][j]=m*n+1;

    if((t[is][js]==1)||(t[id][jd]==1)) g<<"Nu exista solutie"<<endl;
    else
    {
        a[is][js]=0;
        pas=0;
        c=1;
        while(c)
        {
            c=0;
            for(x=1; x<=n; x++)
                for(y=1; y<=m; y++)
                {
                    if(a[x][y]==pas)

                        for(i=0; i<8; i++)
                        {
                            xx=x+dx[i];
                            yy=y+dy[i];
                            if((1<=xx && xx<=n) && (1<=yy && yy<=m) && t[xx][yy]!=1 && a[xx][yy]>pas)
                            {
                                a[xx][yy]=pas+1;
                                c=1;
                            }
                        }

                    if(a[id][jd]!=inf)
                    {
                        x=n;
                        y=m;
                        c=0;
                    }
                }

            pas++;
        } //sf. corp while
        if(a[id][jd]==inf) g<<"Nu exista solutie"<<endl;
        else g<<a[id][jd]<<endl;
    }

    // afisare drum
    // pornesc de la sfarsit spre inceput
    x=id;
    y=jd;
    // in vectorii drumx[] si drumy[] retin coordonatele
    k=1;
    drumx[k]=id;
    drumy[k]=jd;

    while(x!=is&&y!=js)
        for(i=0; i<8; i++)
        {
            xx=x-dx[i];
            yy=y-dy[i];
            if(a[xx][yy]+1==a[x][y])
            {
                k++;
                drumx[k]=xx;
                drumy[k]=yy;
                // actualizez
                x=xx;
                y=yy;
                break; // opresc for
            }
        }
    for(i=k; i>=1; i--)
        g<<drumx[i]<<" "<<drumy[i]<<'\n';

    return 0;
}