Cod sursa(job #2169053)

Utilizator rafaelrafyChitan Rafael rafaelrafy Data 14 martie 2018 13:18:05
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.44 kb
#include <iostream>
#include <fstream>
#include <cstring>
#define ct 100000
using namespace std;
int dl[]={1,0,-1,0,1,1,-1,-1},dc[]={0,1,0,-1,1,-1,1,-1},a[110][110],n,m,j,i,lin1,lin2,col1,col2,rl,rc,jl,jc,b[110][110],minim=ct,imin,jmin;
char s[160];
bool viz[110][110];
struct coada
{
    int lin,col;
}q[20000];
int main()
{
    freopen("rj.in","r",stdin);
    freopen("rj.out","w",stdout);
    cin>>n>>m;
    cin.get();
    for(i=1;i<=n;i++)
    {
        cin.getline(s,150);
        for(j=0;j<m;j++)
        {
            if(s[j]=='R') rl=i,rc=j+1;
            else if(s[j]=='J') jl=i,jc=j+1;
            else if(s[j]=='X') a[i][j+1]=ct,viz[i][j+1]=1;
        }
    }
    q[1].lin=rl;
    q[1].col=rc;
    viz[rl][rc]=1;
    a[rl][rc]=1;
    i=1;
    j=2;
    while(i<=j)
    {
        for(int dr=0;dr<8;dr++)
        {
            lin1=q[i].lin;
            col1=q[i].col;
            lin2=lin1+dl[dr];
            col2=col1+dc[dr];
            if(lin2>=1&&lin2<=n&&col2<=m&&col2>=1&&viz[lin2][col2]==0)
            {
                q[j].lin=lin2;
                q[j].col=col2;
                a[lin2][col2]=a[lin1][col1]+1;
                viz[lin2][col2]=1;
                j++;
            }
        }
        i++;
    }
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
            if(a[i][j]==ct) viz[i][j]=1,b[i][j]=ct;
            else viz[i][j]=0;
        }
    }
    q[1].lin=jl;
    q[1].col=jc;
    viz[jl][jc]=1;
    b[jl][jc]=1;
    i=1;
    j=2;
    while(i<=j)
    {
        for(int dr=0;dr<8;dr++)
        {
            lin1=q[i].lin;
            col1=q[i].col;
            lin2=lin1+dl[dr];
            col2=col1+dc[dr];
            if(lin2>=1&&lin2<=n&&col2<=m&&col2>=1&&viz[lin2][col2]==0)
            {
                q[j].lin=lin2;
                q[j].col=col2;
                b[lin2][col2]=b[lin1][col1]+1;
                viz[lin2][col2]=1;
                j++;
            }
        }
        i++;
    }
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
        {
            if(a[i][j]==b[i][j]&&a[i][j]!=0&&a[i][j]!=ct)
            {
                if(a[i][j]>=0&&a[i][j]<minim) minim=a[i][j],imin=i,jmin=j;
                else if(a[i][j]>=0&&a[i][j]==minim&&i<imin) imin=i,jmin=j;
                else if(a[i][j]>=0&&a[i][j]==minim&&i==imin&&j<jmin) jmin=j;
            }

        }
    cout<<b[imin][jmin]<<' '<<imin<<' '<<jmin;
    return 0;
}