Cod sursa(job #2205269)

Utilizator vladisimovlad coneschi vladisimo Data 18 mai 2018 17:17:15
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.54 kb
#include <fstream>
using namespace std;
ifstream fin("rj.in");
ofstream fout("rj.out");
int dl[8]={-1,-1,0,1,1,1,0,-1};
int dc[8]={0,1,1,1,0,-1,-1,-1};
int n,m,a1[101][101],a2[101][101];
int b1[101][101],b2[101][101];
int xj,yj,xr,yr;
struct nod{
    int l,c,d;
    nod *urm;
};
nod *p,*u;
void cit(){
    int i,j;
    char c;
    fin>>n>>m;
    fin.get();
    for(i=1;i<=n;i++){
        for(j=1;j<=m;j++){
            c=fin.get();
            if(c==' ') a1[i][j]=0;
            else
            if(c=='X') a1[i][j]=1;
            else
            if(c=='J'){ xj=i;yj=j;}
            else
            if(c=='R'){ xr=i;yr=j;}
        }
        fin.get();
    }
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            a2[i][j]=a1[i][j];
}
void lee1(int xs,int ys){
    int i,j,d,in,jn,dn,h;
    nod *q;
    p=0;u=0;
    p=new nod;
    p->l=xs;p->c=ys;
    p->d=1;p->urm=0;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            b1[i][j]=-1;
    b1[xs][ys]=0;
    u=p;
    while(p!=0){
        i=p->l;j=p->c;
        d=p->d;
        for(h=0;h<=7;h++){
            in=i+dl[h];
            jn=j+dc[h];
            dn=d+1;
            if(in>0&&jn>0&&in<n+1&&jn<m+1&&a1[in][jn]==0&&b1[in][jn]==-1){
                b1[in][jn]=dn;
                q=new nod;
                q->l=in;q->c=jn;
                q->d=dn;q->urm=0;
                u->urm=q;u=q;
            }
        }
        q=p;
        p=p->urm;
        delete q;
    }
}
void lee2(int xs,int ys){
    int i,j,d,in,jn,dn,h;
    nod *q;
    p=0;u=0;
    p=new nod;
    p->l=xs;p->c=ys;
    p->d=1;p->urm=0;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            b2[i][j]=-1;
    b2[xs][ys]=0;
    u=p;
    while(p!=0){
        i=p->l;j=p->c;
        d=p->d;
        for(h=0;h<=7;h++){
            in=i+dl[h];
            jn=j+dc[h];
            dn=d+1;
            if(in>0&&jn>0&&in<n+1&&jn<m+1&&a2[in][jn]==0&&b2[in][jn]==-1){
                b2[in][jn]=dn;
                q=new nod;
                q->l=in;q->c=jn;
                q->d=dn;q->urm=0;
                u->urm=q;u=q;
            }
        }
        q=p;
        p=p->urm;
        delete q;
    }
}
int main()
{
    cit();
    lee2(xj,yj);
    lee1(xr,yr);
    int i,j;
    int Min=10000000,poz1,poz2;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            if(b1[i][j]==b2[i][j]&&b1[i][j]<Min&&b1[i][j]!=-1&&b1[i][j]!=0){
                poz1=i;poz2=j;
                Min=b1[i][j];
            }
    fout<<Min<<" "<<poz1<<" "<<poz2;
    return 0;
}