Cod sursa(job #930872)

Utilizator MacWonkMihai Alexandru Cosmin MacWonk Data 27 martie 2013 21:03:44
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.17 kb
#include<fstream>
#include<cstring>
using namespace std;

ifstream f("rj.in");
ofstream g("rj.out");

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

int a[102][102],Nr1[102][102],Nr2[102][102];
int imin,jmin,n,m,i,j,lp1,lp2,cp1,cp2,y,x,minim;
int p, u, la, ca, lv, cv;
char aux[1000];

struct coada
{
    int l,c;
}C[10000];

int main()
{
    f>>n>>m;
    for (i=0;i<=n;++i)
        {
            a[i][0]=-1;
            a[i][m+1]=-1;
        }
    for (i=0;i<=m;++i)
    {
        a[0][i]=-1;
        a[n+1][i]=-1;
    }
    f.get();
    for(i=1;i<=n;++i)
    {
        f.getline(aux,1001);
        for (j=1;j<=m;++j)
        {
            if(aux[j-1]==' ') a[i][j]=0;
                else if (aux[j-1]=='X') a[i][j]=1;

            if(aux[j-1]=='R') {lp1=i;cp1=j;}
                else if (aux[j-1]=='J') {lp2=i;cp2=j;}

                Nr1[i][j]=999999;
                Nr2[i][j]=999999;
        }
    }
     int p, u, la, ca, i, lv, cv;
    C[1].l=lp1; C[1].c=cp1;
    Nr1[lp1][cp1]=1;
    p=1; u=1;
    while (p<=u)
    {
       la=C[p].l;
       ca=C[p].c;
       for (i=0;i<8;i++)
        {
            lv=la+dx[i];
            cv=ca+dy[i];
            if (a[lv][cv]==0 &&  Nr1[lv][cv]>Nr1[la][ca]+1)
            {
                ++u;
                C[u].l=lv;
                C[u].c=cv;
                Nr1[lv][cv]=1+Nr1[la][ca];
            }
        }
        ++p;
    }
    C[1].l=lp2; C[1].c=cp2;
    la=0;ca=0;i=0;lv=0;cv=0;
    Nr2[lp2][cp2]=1;
    p=1;u=1;
    while (p<=u)
    {
       la=C[p].l;
       ca=C[p].c;
       for (i=0;i<8;i++)
        {
            lv=la + dx[i];
            cv=ca + dy[i];
            if (a[lv][cv] == 0 &&  Nr2[lv][cv]>Nr2[la][ca]+1)
            {
                ++u;
                C[u].l=lv;
                C[u].c=cv;
                Nr2[lv][cv]=1+Nr2[la][ca];
            }
        }
        ++p;
    }
    minim=100000;
    for (i=1;i<=n;++i)
        for (j=1;j<=m;++j)
            if (Nr1[i][j]==Nr2[i][j]&&Nr1[i][j]!=999999)
                if (Nr1[i][j]<minim) {minim=Nr1[i][j];imin=i;jmin=j;}
    g<<minim<<" "<<imin<<" "<<jmin;
    return 0;

}