Cod sursa(job #930524)

Utilizator margikiMargeloiu Andrei margiki Data 27 martie 2013 18:11:06
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.71 kb
# include <fstream>
# include <algorithm>
# include <cstring>
using namespace std;
ifstream f("rj.in");
ofstream g("rj.out");
int i,k,x1,x2,n,m,y1,y2,v1,v2,smax;
char c;
short a[102][102], b[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;
    a[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 && a[lv][cv]>a[la][ca]+1)
            {
                ++u; //punem in coada
                r[u].l=lv; r[u].c=cv;
                a[lv][cv]=1+a[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;
    b[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 (b[lv][cv]==0 && b[lv][cv]>b[la][ca]+1)
            {
                ++u; //punem in coada
                j[u].l=lv; j[u].c=cv;
                b[lv][cv]=1+b[la][ca];
            }
        }
        ++p;
    }
}
int main ()
{
    f>>n>>m;
    f.get ();
    for (i=1; i<=n; ++i)
    {
        for (k=1; k<=m; ++k)
        {
            f>>c;
            if (c=='X') {
                            a[i][k]=-1;
                            b[i][k]=-1;
                        }
            if (c=='R'){
                            x1=i;
                            y1=k;
                       }
            if (c=='J'){
                            x2=i;
                            y2=k;
                       }
        }
        f.get ();
    }

    for (i=0; i<=n+1; ++i)
	{
        a[i][0]=1; a[i][m+1]=1;
        b[i][0]=1; b[i][m+1]=1;
	}

	for (i=0; i<=m+1; ++i)
	{
	    a[0][i]=1; a[n+1][i]=1;
	    b[0][i]=1; b[n+1][i]=1;
	}
	smax=500000;
	leer (x1,y1);
	leej (x2,y2);
	for (i=1; i<=n; ++i)
	    for (k=1; k<=m; ++k)
	        if (a[i][k]==b[i][k] && a[i][k]!=-1) if (a[i][k]<smax) {
                                                                       smax=a[i][k];
                                                                       v1=i;
                                                                       v2=k;
                                                                   }
    g<<v1<<" "<<v2<<" "<<smax<<"\n";
    for (i=1; i<=n; ++i)
    {
        for (k=1; k<=m; ++k)
            g<<a[i][k];
        g<<"\n";
    }
    return 0;
}