Cod sursa(job #1095018)

Utilizator serban_ioan97Ciofu Serban serban_ioan97 Data 30 ianuarie 2014 11:11:54
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.21 kb
# include <fstream>
# include <cstring>
# define inf 1000000

using namespace std;

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

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

int Nrr[13][130], Nrj[130][130];
int n, m, i, j, xr, yr, xj, yj, x, y, Min, A[140][140];
char c, a[130][130];
struct coada
{
    int l, c;
}C[100001];

void leer(int x, int y)
{
    int p, u, la, ca, i, lv, cv;

    C[1].l=x; C[1].c=y;
    Nrr[x][y] = 1;
    p=1; u=1;
    while (p<=u)
    {

       la = C[p].l;
       ca = C[p].c;

       for (i=1; i<=8; i++)
        {
            lv = la + dx[i];
            cv = ca + dy[i];

            if (A[lv][cv] ==1 && Nrr[lv][cv] > Nrr[la][ca] + 1)
            {
                ++u;
                C[u].l=lv; C[u].c=cv;
                Nrr[lv][cv] = 1 + Nrr[la][ca];
            }
        }
        ++p;
    }
}

void leej(int x, int y)
{
    int p, u, la, ca, i, lv, cv;

    C[1].l=x; C[1].c=y;
    Nrj[x][y] = 1;
    p=1; u=1;
    while (p<=u)
    {

       la = C[p].l;
       ca = C[p].c;

       for (i=1; i<=8; i++)
        {
            lv = la + dx[i];
            cv = ca + dy[i];

            if (A[lv][cv] ==0 && Nrj[lv][cv] > Nrj[la][ca] + 1)
            {
                ++u;
                C[u].l=lv; C[u].c=cv;
                Nrj[lv][cv] = 1 + Nrj[la][ca];
            }
        }
        ++p;
    }
}
int main()
{
    f>>n>>m;
    f.get();
   for (i=1; i<=n; i++)
    {
        for (j=1; j<=m; j++)
        {   Nrr[i][j]=Nrj[i][j]=inf;
            f.get(c); a[i][j]=c;
             if (a[i][j]=='R') {xr=i; yr=j; a[i][j]=' ';}
             if (a[i][j]=='J') {xj=i; yj=j; a[i][j]=' ';}
		}
        f.get(c);
	}
    for(i=1; i<=n; i++)
        for(j=1; j<=n; j++)
            if(a[i][j]=='X') A[i][j]=1;
            else A[i][j]=0;

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

    for(j=0; j<=m+1; j++)
        A[0][j]=A[n+1][j]=1;

    leer(xr, yr);
    leej(xj, yj);

    Min=inf;

    for(i=1; i<=n; i++)
        for(j=1; j<=m; j++)
            if(Nrr[i][j]==Nrj[i][j]&&Nrr[i][j]!=inf&&Nrj[i][j]!=inf) if(Nrr[i][j]<Min) {Min=Nrr[i][j]; x=i; y=j;}

    g<<Min<<" "<<x<<" "<<y;
}