Cod sursa(job #1338196)

Utilizator dariusdariusMarian Darius dariusdarius Data 9 februarie 2015 20:54:59
Problema Rj Scor 100
Compilator cpp Status done
Runda simulareoji2015cl10 Marime 2.18 kb
#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;
int r[105][105],jl[105][105];
int dx[]={0,-1,-1,0,1,1,1,0,-1};
int dy[]={0,0,1,1,1,0,-1,-1,-1};
struct STRUCT {int x,y;};
queue<STRUCT> q;
STRUCT temp,rom,jul;
char s[105];
int u;
int  main()
{
    freopen("rj.in","r",stdin);
    freopen("rj.out","w",stdout);
    int n,m,i,j;
    char ch;
    scanf("%d%d\n",&n,&m);
    for(i=0;i<=n+1;i++)
        r[i][0]=r[i][m+1]=jl[i][0]=jl[i][m+1]=-1;
    for(j=0;j<=m+1;j++)
        r[0][j]=r[n+1][j]=jl[0][j]=jl[n+1][j]=-1;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            r[i][j]=jl[i][j]=-2;
    for(i=1;i<=n;i++)
    {
    gets(s);
    u=strlen(s);
    if(u<m)
        while(u<m)
        {
            strcat(s," ");
            u++;
        }
    for(j=0;j<u;j++)
    {
        ch=s[j];
        if(ch=='R')
            {r[i][j+1]=1;rom.x=i;rom.y=j+1;}
        if(ch=='J')
            {jl[i][j+1]=1;jul.x=i;jul.y=j+1;}
        if(ch==' ')
            continue;
        if(ch=='X')
            r[i][j+1]=jl[i][j+1]=-1;
    }
    }
    //Lee pentru Romeo:
    temp.x=rom.x;
    temp.y=rom.y;
    q.push(temp);
    while(!q.empty())
    {
        for(i=1;i<=8;i++)
        {
            temp.x=q.front().x+dx[i];
            temp.y=q.front().y+dy[i];
            if(r[temp.x][temp.y]==-2)
                {q.push(temp);r[temp.x][temp.y]=r[q.front().x][q.front().y]+1;}
        }
        q.pop();
    }
    while(!q.empty())
        q.pop();
    //Lee pentru Julieta:
    temp.x=jul.x;
    temp.y=jul.y;
    q.push(temp);
    while(!q.empty())
    {
        for(i=1;i<=8;i++)
        {
            temp.x=q.front().x+dx[i];
            temp.y=q.front().y+dy[i];
            if(jl[temp.x][temp.y]==-2)
                {q.push(temp);jl[temp.x][temp.y]=jl[q.front().x][q.front().y]+1;}
        }
        q.pop();
    }
    //Finalizare:
    STRUCT min;
    int mm=1000000000;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            if(r[i][j]==jl[i][j] && r[i][j]!=-1 && r[i][j]!=-2)
                if(r[i][j]<mm)
                {mm=r[i][j];min.x=i;min.y=j;}

    printf("%d %d %d",mm,min.x,min.y);
    return 0;
}