Cod sursa(job #744745)

Utilizator mirceadinoMircea Popoveniuc mirceadino Data 9 mai 2012 16:18:47
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.14 kb
#include<cstdio>
#include<deque>
#include<utility>
using namespace std;
int check(int x,int y,int xp,int yp)
{
    if(x==xp && y==yp) return 1;
    else return 0;
}
int main()
{
    int a[102][102],b[102][102],ok=0,i,j,m,n,Rx,Ry,Jx,Jy,x,y,min=100000,X=105,Y=105;
    deque< pair<int,int> > DQ;
    char c,s[102];
for(i=0;i<=100;i++)
    for(j=0;j<=100;j++) {a[i][j]=-1; b[i][j]=-1;}
freopen("rj.in","r",stdin);
freopen("rj.out","w",stdout);
scanf("%d%d%c",&n,&m,&c);
for(i=1;i<=n;i++)
{
    gets(s);
    for(j=1;j<=m;j++)
    {
        c=s[j-1];
        if(c=='X') {a[i][j]=0; b[i][j]=0;}
        else if(c=='R') {a[i][j]=1; Rx=i; Ry=j;}
        else if(c=='J') {b[i][j]=1; Jx=i; Jy=j;}
    }
}
/*for(i=1;i<=n;i++)
{
    for(j=1;j<=m;j++)
        printf("%d ",a[i][j]);
    printf("\n");
}
printf("--------------------\n");*/
DQ.push_back(make_pair(Rx,Ry));
for(ok=1;ok<=4;ok++)
{
    j=DQ.size();
    for(i=0;i<j;i++)
    {
        x=DQ.front().first; y=DQ.front().second; DQ.pop_front();
        if(a[x-1][y-1]==(-1))//&&(x-1>0&&y-1>0&&x-1<=n&&y-1<=m))
            {a[x-1][y-1]=a[x][y]+1; DQ.push_back(make_pair(x-1,y-1)); ok=check(Jx,Jy,x-1,y-1);}
        if(a[x-1][y]==(-1))//&&(x-1>0&&y>0&&x-1<=n&&y<=m))
            {a[x-1][y]=a[x][y]+1; DQ.push_back(make_pair(x-1,y)); ok=check(Jx,Jy,x-1,y);}
        if(a[x-1][y+1]==(-1))//&&(x-1>0&&y+1>0&&x-1<=n&&y+1<=m))
            {a[x-1][y+1]=a[x][y]+1; DQ.push_back(make_pair(x-1,y+1)); ok=check(Jx,Jy,x-1,y+1);}
        if(a[x][y-1]==(-1))//&&(x>0&&y-1>0&&x<=n&&y-1<=m))
            {a[x][y-1]=a[x][y]+1; DQ.push_back(make_pair(x,y-1)); ok=check(Jx,Jy,x,y-1);}
        if(a[x][y+1]==(-1))//&&(x>0&&y+1>0&&x<=n&&y+1<=m))
            {a[x][y+1]=a[x][y]+1; DQ.push_back(make_pair(x,y+1)); ok=check(Jx,Jy,x,y+1);}
        if(a[x+1][y-1]==(-1))//&&(x+1>0&&y-1>0&&x+1<=n&&y-1<=m))
            {a[x+1][y-1]=a[x][y]+1; DQ.push_back(make_pair(x+1,y-1)); ok=check(Jx,Jy,x+1,y-1);}
        if(a[x+1][y]==(-1))//&&(x+1>0&&y>0&&x+1<=n&&y<=m))
            {a[x+1][y]=a[x][y]+1; DQ.push_back(make_pair(x+1,y)); ok=check(Jx,Jy,x+1,y);}
        if(a[x+1][y+1]==(-1))//&&(x+1>0&&y+1>0&&x+1<=n&&y+1<=m))
            {a[x+1][y+1]=a[x][y]+1; DQ.push_back(make_pair(x+1,y+1)); ok=check(Jx,Jy,x+1,y+1);}
    }
}
/*for(i=1;i<=n;i++)
{
    for(j=1;j<=m;j++)
        printf("%d ",a[i][j]);
    printf("\n");
}
printf("--------------------\n");*/
DQ.resize(0);
DQ.push_back(make_pair(Jx,Jy));
for(ok=1;ok<=4;ok++)
{
    j=DQ.size();
    for(i=0;i<j;i++)
    {
        x=DQ.front().first; y=DQ.front().second; DQ.pop_front();
        if(b[x-1][y-1]==(-1))//&&(x-1>0&&y-1>0&&x-1<=n&&y-1<=m))
            {b[x-1][y-1]=b[x][y]+1; DQ.push_back(make_pair(x-1,y-1)); ok=check(Rx,Ry,x-1,y-1);}
        if(b[x-1][y]==(-1))//&&(x-1>0&&y>0&&x-1<=n&&y<=m))
            {b[x-1][y]=b[x][y]+1; DQ.push_back(make_pair(x-1,y)); ok=check(Rx,Ry,x-1,y);}
        if(b[x-1][y+1]==(-1))//&&(x-1>0&&y+1>0&&x-1<=n&&y+1<=m))
            {b[x-1][y+1]=b[x][y]+1; DQ.push_back(make_pair(x-1,y+1)); ok=check(Rx,Ry,x-1,y+1);}
        if(b[x][y-1]==(-1))//&&(x>0&&y-1>0&&x<=n&&y-1<=m))
            {b[x][y-1]=b[x][y]+1; DQ.push_back(make_pair(x,y-1)); ok=check(Rx,Ry,x,y-1);}
        if(b[x][y+1]==(-1))//&&(x>0&&y+1>0&&x<=n&&y+1<=m))
            {b[x][y+1]=b[x][y]+1; DQ.push_back(make_pair(x,y+1)); ok=check(Rx,Ry,x,y+1);}
        if(b[x+1][y-1]==(-1))//&&(x+1>0&&y-1>0&&x+1<=n&&y-1<=m))
            {b[x+1][y-1]=b[x][y]+1; DQ.push_back(make_pair(x+1,y-1)); ok=check(Rx,Ry,x+1,y-1);}
        if(b[x+1][y]==(-1))//&&(x+1>0&&y>0&&x+1<=n&&y<=m))
            {b[x+1][y]=b[x][y]+1; DQ.push_back(make_pair(x+1,y)); ok=check(Rx,Ry,x+1,y);}
        if(b[x+1][y+1]==(-1))//&&(x+1>0&&y+1>0&&x+1<=n&&y+1<=m))
            {b[x+1][y+1]=b[x][y]+1; DQ.push_back(make_pair(x+1,y+1)); ok=check(Rx,Ry,x+1,y+1);}
    }
}
/*for(i=1;i<=n;i++)
{
    for(j=1;j<=m;j++)
        printf("%d ",b[i][j]);
    printf("\n");
}
printf("--------------------\n");*/
for(i=1;i<=n;i++)
{
    for(j=1;j<=m;j++)
        if(a[i][j]==b[i][j]&&a[i][j]!=0)
        {
            if(a[i][j]<min) {min=a[i][j]; X=i; Y=j;}
        }
}
printf("%d %d %d\n",min,X,Y);
return 0;
}