Cod sursa(job #1624322)

Utilizator pepsiM4A1Ozturk Arif pepsiM4A1 Data 2 martie 2016 10:19:07
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.32 kb
#include <cstdio>
char ch[123];
int v[123][123],d[123][123][2],n,m;
bool vis[123][123][2];
int dx[8]={-1,1,0,0,-1,1,-1,1},dy[8]={0,0,-1,1,-1,1,1,-1};
struct str
{
    int p1;
    int p2;
}q[10023];
int ps=1;
int accesibil(int p1,int p2,int caz)
{
    if(p1<1) return 0;
    if(p1>n) return 0;
    if(p2<1) return 0;
    if(p2>m) return 0;
    if(vis[p1][p2][caz]||v[p1][p2]) return 0;
    return 1;
}
void bfs(int caz)
{
    vis[q[1].p1][q[1].p2][caz]=1;
    for(int pt=1;pt<=ps;pt++)
    {
        for(int i=0;i<8;i++)
        {
            if(accesibil(q[pt].p1+dx[i],q[pt].p2+dy[i],caz))
            {
                vis[q[pt].p1+dx[i]][q[pt].p2+dy[i]][caz]=1;
                d[q[pt].p1+dx[i]][q[pt].p2+dy[i]][caz]=d[q[pt].p1][q[pt].p2][caz]+1;
                q[++ps].p1=q[pt].p1+dx[i];
                q[ps].p2=q[pt].p2+dy[i];
            }
        }
    }
}
int main()
{
    freopen ("rj.in","r",stdin);
    freopen ("rj.out","w",stdout);
    int p1,p2,p3,p4;
    scanf("%d%d",&n,&m);
    gets(ch);
    for(int i=1;i<=n;i++)
    {
        gets(ch);
        for(int j=1;j<=m;j++)
        {
            if(ch[j-1]=='X') v[i][j]=1;
            else if(ch[j-1]=='R')
            {
                p1=i;
                p2=j;
            }
            else if(ch[j-1]=='J')
            {
                p3=i;
                p4=j;
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            d[i][j][0]=-1;
            d[i][j][1]=-1;
        }
    }
    d[p1][p2][0]=0;
    d[p3][p4][1]=0;
    q[1].p1=p1;
    q[1].p2=p2;
    ps=1;
    bfs(0);
    q[1].p1=p3;
    q[1].p2=p4;
    ps=1;
    bfs(1);
    int minim=1000000000,px=0,py=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(d[i][j][0]==d[i][j][1]&&d[i][j][0]>0&&v[i][j]==0)
            {
                if(minim>d[i][j][0])
                {
                    minim=d[i][j][0];
                    px=i;
                    py=j;
                }
                else if(minim==d[i][j][0]&&px>i)
                {
                    px=i;
                    py=j;
                }
                else if(minim==d[i][j][0]&&px==i&&py>j) py=j;
            }
        }
    }
    printf("%d %d %d\n",minim+1,px,py);
}