Cod sursa(job #2064429)

Utilizator SchnitzelMannPavaloiu Gabriel SchnitzelMann Data 12 noiembrie 2017 12:53:55
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.1 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream in("rj.in");
ofstream out("rj.out");
const int N=102;
const int dl[]={-1,-1,0,1,1,1,0,-1};
const int dc[]={0,1,1,1,0,-1,-1,-1};
struct comp{
    short int l,c;
};
comp q[N*N];
int a[N][N];
int b[N][N];
int main()
{
    string idk;
    int n,m,i,j,p,u,timp=2000000000,x,y;
    comp R,J,curent,vecin;
    in>>n>>m;
    for(i=0;i<=n+1;i++)
    {
        a[i][0]=-1;
        a[i][m+1]=-1;
        b[i][0]=-1;
        b[i][m+1]=-1;
    }
    for(i=0;i<=m+1;i++)
    {
        a[0][i]=-1;
        a[n+1][i]=-1;
        b[0][i]=-1;
        b[n+1][i]=-1;
    }
    getline(in,idk);
    for(i=1;i<=n;i++)
    {
        getline(in,idk);
        for(j=1;j<=m;j++)
        {
            if(idk[j-1]=='X')
                a[i][j]=b[i][j]=-1;
            else if(idk[j-1]=='R')
            {
                R.l=i;
                R.c=j;
            }
            else if(idk[j-1]=='J')
            {
                J.l=i;
                J.c=j;
            }
        }
    }
    p=0;u=-1;
    q[++u]=R;
    a[R.l][R.c]=1;
    while(p<=u)
    {
        curent=q[p++];
        for(i=0;i<8;i++)
        {
            vecin.l=curent.l+dl[i];
            vecin.c=curent.c+dc[i];
            if(a[vecin.l][vecin.c]==0)
            {
                q[++u]=vecin;
                a[vecin.l][vecin.c]=1+a[curent.l][curent.c];
            }
        }
    }
    p=0;u=-1;
    q[++u]=J;
    b[J.l][J.c]=1;
    while(p<=u)
    {
        curent=q[p++];
        for(i=0;i<8;i++)
        {
            vecin.l=curent.l+dl[i];
            vecin.c=curent.c+dc[i];
            if(b[vecin.l][vecin.c]==0)
            {
                q[++u]=vecin;
                b[vecin.l][vecin.c]=1+b[curent.l][curent.c];
            }
            if(a[vecin.l][vecin.c]==b[vecin.l][vecin.c]&&a[vecin.l][vecin.c]>0&&a[vecin.l][vecin.c]<timp)
            {
                x=vecin.l;
                y=vecin.c;
                timp=a[vecin.l][vecin.c];
            }
        }
    }
    out<<timp<<" "<<x<<" "<<y;
    return 0;
}