Cod sursa(job #1367704)

Utilizator cipriancxFMI - gr143 Timofte Ciprian cipriancx Data 2 martie 2015 01:00:34
Problema Rj Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.19 kb
#include <iostream>
#include <cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;

char linie[111];
int n,m,tmin=100000,a,b,ri,rj,ji,jj,ti,tj;

typedef struct {
int i;
int j;
}pereche;

pereche coada[12100];
int startc,stopc;
char oras[110][110];
int viz[110][110],distr[110][110],distj[110][110];

int valid(int i,int j)
{
    if(i<1)return 0;
    if(i>n)return 0;
    if(j<1)return 0;
    if(j>m)return 0;
    if(viz[i][j])return 0;
    if(oras[i][j]!=' ')return 0;
    return 1;
}


int main()
{
  FILE *f=freopen("rj.in","r",stdin);
 freopen("rj.out","w",stdout);

fgets(linie,110,f);
sscanf(linie,"%d %d",&n,&m);



for(int i=1; i<=n; i++)
{
    fgets(linie,110,f);

   for(int j=0; j<m; j++)
    {oras[i][j+1]=linie[j];
    if(oras[i][j]=='R'){ ri=i; rj=j; }
    if(oras[i][j]=='J'){ ji=i; jj=j; }

    }

}

//calculam distantele de la Romeo
distr[ri][rj]=0;
viz[ri][rj]=1;
for(int i=-1; i<=1; i++)
    for(int j=-1; j<=1; j++)
    if(valid(ri+i,rj+j)){ stopc++; coada[stopc].i=ri+i; coada[stopc].j=rj+j; distr[ri+i][rj+j]=1; viz[ri+i][rj+j]=1;   }

while(startc<=stopc)
{
    int a=coada[startc].i;
    int b=coada[startc].j;
    for(int i=-1; i<=1; i++)
        for(int j=-1; j<=1; j++)if(valid(a+i,b+j)){ stopc++; coada[stopc].i=a+i; coada[stopc].j=b+j; distr[a+i][b+j]=distr[a][b]+1; viz[a+i][b+j]=1;   }
  startc++;
}


for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)viz[i][j]=0;

//completam pt julieta
startc=stopc=0;


distj[ji][jj]=0;
viz[ji][jj]=1;
for(int i=-1; i<=1; i++)
    for(int j=-1; j<=1; j++)
    if(valid(ji+i,jj+j)){ stopc++; coada[stopc].i=ji+i; coada[stopc].j=jj+j; distj[ji+i][jj+j]=1; viz[ji+i][jj+j]=1;   }

while(startc<=stopc)
{
    int a=coada[startc].i;
    int b=coada[startc].j;
    for(int i=-1; i<=1; i++)
        for(int j=-1; j<=1; j++)if(valid(a+i,b+j)){ stopc++; coada[stopc].i=a+i; coada[stopc].j=b+j; distj[a+i][b+j]=distj[a][b]+1; viz[a+i][b+j]=1;   }
  startc++;
}

for(int i=1; i<=n; i++)
{
    for(int j=1; j<=m; j++)if(distr[i][j]==distj[i][j] && distr[i][j]<tmin && distr[i][j]){tmin=distr[i][j]; ti=i; tj=j; }
}

printf("%d %d %d\n",tmin+1,ti,tj);



    return 0;
}