Cod sursa(job #1125509)

Utilizator mmc170597Marin Mihnea Cristian mmc170597 Data 26 februarie 2014 18:03:39
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.13 kb
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
struct coord
{
  int x,y;
};
int r[101][101];
int J[101][101];
int di[]={0,1,1,1,0,-1,-1,-1,0};
int dj[]={0,0,1,1,1,0,-1,-1,-1};
queue<coord> q;
coord ro,ju;
int n,m,i,j;
char c[1001];
void bordare()
{
    int i,j;
    for(i=0;i<=n+2;i++){ r[i][0]=-1; J[i][0]=-1; r[i][m+1]=-1; J[i][m+1]=-1; }
    for(j=0;j<=m+2;j++){ r[0][j]=-1; r[n+1][j]=-1; J[0][j]=-1; J[n+1][j]=-1; }
}
void romeo(coord location)
{
    coord w;
    if(location.x>=0&&location.y>=0)
    {
    if(r[location.x][location.y]==0)
    {
        w=q.front();
        r[location.x][location.y]=r[w.x][w.y]+1;
        q.push(location);
    }
    }
}
void juliet(coord location)
{
    coord w;
    if(location.x>=0&&location.y>=0)
    {
    if(J[location.x][location.y]==0)
    {
        w=q.front();
        J[location.x][location.y]=J[w.x][w.y]+1;
        q.push(location);
    }
    }
}
void lee(coord inceput,int caz)
{
    int i;
    coord target;

    q.push(inceput);
    while(!q.empty())
    {
        for(i=1;i<=8;i++)
        {
            target=q.front();
            target.x+=di[i];
            target.y+=dj[i];

            if(caz==1)
                romeo(target);
            else
                juliet(target);
        }
        q.pop();
    }
}
int main()
{
    freopen("rj.in","r",stdin);
    freopen("rj.out","w",stdout);
    int min;
    coord meeting;
    scanf("%d%d\n",&n,&m);
    bordare();
    for(i=1;i<=n;i++)
    {
        gets(c);
        for(j=1;j<=m;j++)
        {
            if(c[j-1]=='J'){ ju.x=i; ju.y=j;}
            if(c[j-1]=='R'){ ro.x=i; ro.y=j;}
            if(c[j-1]=='X'){ r[i][j]=-1; J[i][j]=-1;}
        }
    }
    r[ro.x][ro.y]=1;
    J[ju.x][ju.y]=1;
    lee(ro,1);
    lee(ju,2);
    min=n*m+1;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            if(r[i][j]==J[i][j]&&min>r[i][j]&&r[i][j]>0)
            {
                min=r[i][j];
                meeting.x=i;
                meeting.y=j;
            }
    printf("%d %d %d\n",min,meeting.x,meeting.y);
    return 0;
}