Cod sursa(job #1608631)

Utilizator ana-maria.simiAna-Maria Simionescu ana-maria.simi Data 22 februarie 2016 11:25:32
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.12 kb
#include <iostream>
#include <fstream>
using namespace std;
int a[101][101],b[101][101],i,j,n,m,dl[]={-1,-1,0,1,1,1,0,-1},dc[]={0,1,1,1,0,-1,-1,-1},prim,ultim,k,minim,pi,pj;
char c;
struct pozitie {int lin,col;}q[10010],psr,pcr,p,v,psj,pcj;
int main()
{freopen("rj.in", "r", stdin);
freopen("rj.out", "w", stdout);
scanf("%d%d\n", &n, &m);
for(i=1; i<=n; i++)
    {for(j=1; j<=m; j++)
        {scanf("%c", &c);
        if(c=='X')
            b[i][j]=a[i][j]=-1;
        if(c==' ')
            b[i][j]=a[i][j]=0;
        if(c=='R')
            {b[i][j]=a[i][j]=0;
            psr.lin=i;
            psr.col=j;
            pcj.lin=i;
            pcj.col=j;}
        if(c=='J')
            {b[i][j]=a[i][j]=0;
            pcr.lin=psj.lin=i;
            pcr.col=psj.col=j;}}
    scanf("\n");}
//for(i=1; i<=n; i++)
//    {for(j=1; j<=m; j++)
//        cout<<a[i][j]<<" ";
//    cout<<'\n';}
//for(i=1; i<=n; i++)
//    {for(j=1; j<=m; j++)
//        cout<<b[i][j]<<" ";
//    cout<<'\n';}
for(j=0; j<=m+1; j++)
    a[0][j]=b[0][j]=-1;
for(i=0; i<=n+1; i++)
    a[i][m+1]=b[i][m+1]=-1;
for(j=m+1; j>=0; j--)
    a[n+1][j]=b[n+1][j]=-1;
for(i=n+1; i>=0; i--)
    a[i][0]=b[i][0]=-1;
prim=ultim=0;
q[prim]=psr;
a[psr.lin][psr.col]=1;
while(prim<=ultim && a[pcr.lin][pcr.col]==0)
    {p=q[prim];
    prim++;
    for(k=0; k<8; k++)
        {v.lin=p.lin+dl[k];
        v.col=p.col+dc[k];
        if(a[v.lin][v.col]==0)
            {a[v.lin][v.col]=a[p.lin][p.col]+1;
            q[++ultim]=v;}}}
prim=ultim=0;
q[prim]=psj;
b[psj.lin][psj.col]=1;
while(prim<=ultim && b[pcj.lin][pcj.col]==0)
    {p=q[prim];
    prim++;
    for(k=0; k<8; k++)
        {v.lin=p.lin+dl[k];
        v.col=p.col+dc[k];
        if(b[v.lin][v.col]==0)
            {b[v.lin][v.col]=b[p.lin][p.col]+1;
            q[++ultim]=v;}}}
minim=10010;
for(i=1; i<=n; i++)
    for(j=1; j<=m; j++)
        if(a[i][j]!=0 && a[i][j]!=-1)
            if(a[i][j]==b[i][j])
                if(a[i][j]<minim)
                    {minim=a[i][j];
                    pi=i;
                    pj=j;}
cout<<minim<<" "<<pi<<" "<<pj;
    return 0;
}