Cod sursa(job #930744)

Utilizator margikiMargeloiu Andrei margiki Data 27 martie 2013 19:58:10
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.57 kb
# include <fstream>
# include <algorithm>
# include <cstring>
# define inf 10000
using namespace std;
ifstream f("rj.in");
ofstream g("rj.out");
int i,k,x1,x2,n,m,y1,y2,v1,v2,smax,lungime;
char c,VV[128];
short a[102][102], Nr1[102][102], Nr2[102][102];
int dx[]={-1,-1,0,1,1,1,0,-1};
int dy[]={0,1,1,1,0,-1,-1,-1};
struct julieta
{
    int l,c;
}j[10001];
struct romeo
{
    int l,c;
}r[10001];
void leer (int x, int y)
{
    int p,u,la,ca,i,lv,cv;
    r[1].l=x; r[1].c=y;
    Nr1[x][y]=1;
    p=1; u=1;
    while (p<=u)
    {
       la=r[p].l;
       ca=r[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;
                r[u].l=lv;
                r[u].c=cv;
                Nr1[lv][cv]=1+Nr1[la][ca];
            }
        }
        ++p;
    }
}
void leej (int x, int y)
{
    int p,u,la,ca,i,lv,cv;
    j[1].l=x; j[1].c=y;
    Nr2[x][y]=1;
    p=1; u=1;
    while (p<=u)
    {
       la=j[p].l;
       ca=j[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;
                j[u].l=lv;
                j[u].c=cv;
                Nr2[lv][cv]=1+Nr2[la][ca];
            }
        }
        ++p;
    }
}
int main ()
{
    f>>n>>m;
    f.get ();
    for (i=1; i<=n; ++i)
    {
        f.getline(VV,128);
        lungime=strlen(VV);
        for (k=0; k<m; ++k)
        {
            c=VV[k];
            if (c=='X') a[i][k+1]=-1;

            if (c=='R'){
                            x1=i;
                            y1=k+1;
                       }
            if (c=='J'){
                            x2=i;
                            y2=k+1;
                       }
            Nr1[i][k+1]=inf;
            Nr2[i][k+1]=inf;
        }
    }

    for (i=0; i<=n+1; ++i)
        a[i][0]=-1; a[i][m+1]=-1;

	for (i=0; i<=m+1; ++i)
	    a[0][i]=-1; a[n+1][i]=-1;

	smax=5000;
	leer (x1,y1);
    leej (x2,y2);

    for (i=1; i<=n; ++i)
       for (k=1; k<=m; ++k)
           if (Nr1[i][k]==Nr2[i][k] && Nr1[i][k]<smax) {
                                                           smax=Nr1[i][k];
                                                           v1=i;
                                                           v2=k;
                                                       }
    g<<smax<<" "<<v1<<" "<<v2<<"\n";
    return 0;
}