Cod sursa(job #1650610)

Utilizator dominiciorgandaDominic Iorganda dominiciorganda Data 11 martie 2016 19:19:31
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.85 kb
#include <iostream>
#include <fstream>
#include <queue>
using namespace std;
string f[105],h1;
short g[105][105],h[105][105],k,i,m,x,cmin,j,ct,k1,i1,k2,i2,xc,mc,xu,mu,k3,i3;
queue<int>qx,qm;
bool verif(int k,int i,int x, int m)
{
    if(k>=0&&k<x&&i>=0&&i<m)
        return 1;
    return 0;
}
void lee(int xc,int mc,int xu ,int mu)
{
    if(verif(xu,mu,x,m)&&f[xu][mu]!='X')
    {
        if(g[xu][mu]>=g[xc][mc]+2)
        {
            g[xu][mu]=g[xc][mc]+1;
            qx.push(xu); qm.push(mu);
        }
    }
}
void lee2(int xc,int mc,int xu ,int mu)
{
    if(verif(xu,mu,x,m)&&f[xu][mu]!='X')
    {
        if(h[xu][mu]>=h[xc][mc]+2)
        {
            h[xu][mu]=h[xc][mc]+1;
            qx.push(xu); qm.push(mu);
        }
    }
}
int main()
{
    ifstream fin("rj.in");
    ofstream fout("rj.out");
    fin>>x>>m;
    getline(fin,h1);
    for(k=0;k<x;k++)
        getline(fin,f[k]);
    for(k=0;k<x;k++)
    {
        for(i=0;i<m;i++)
        {
            g[k][i]=h[k][i]=x*x+5;
            if(f[k][i]=='R')
            {
                k1=k;
                i1=i;
            }
            if(f[k][i]=='J')
            {
                k2=k;
                i2=i;
            }
        }
    }
    for(g[k1][i1]=0,qx.push(k1),qm.push(i1);!qx.empty();)
    {
        xc=qx.front(); mc=qm.front();
        qx.pop(); qm.pop();
        xu=xc+1; mu=mc; lee(xc,mc,xu,mu);
        xu=xc; mu=mc+1; lee(xc,mc,xu,mu);
        xu=xc-1; mu=mc; lee(xc,mc,xu,mu);
        xu=xc; mu=mc-1; lee(xc,mc,xu,mu);
        xu=xc+1; mu=mc+1; lee(xc,mc,xu,mu);
        xu=xc+1; mu=mc-1; lee(xc,mc,xu,mu);
        xu=xc-1; mu=mc+1; lee(xc,mc,xu,mu);
        xu=xc-1; mu=mc-1; lee(xc,mc,xu,mu);
    }
    for(h[k2][i2]=0,qx.push(k2),qm.push(i2);!qx.empty();)
    {
        xc=qx.front(); mc=qm.front();
        qx.pop(); qm.pop();
        xu=xc+1; mu=mc; lee2(xc,mc,xu,mu);
        xu=xc; mu=mc+1; lee2(xc,mc,xu,mu);
        xu=xc-1; mu=mc; lee2(xc,mc,xu,mu);
        xu=xc; mu=mc-1; lee2(xc,mc,xu,mu);
        xu=xc+1; mu=mc+1; lee2(xc,mc,xu,mu);
        xu=xc+1; mu=mc-1; lee2(xc,mc,xu,mu);
        xu=xc-1; mu=mc+1; lee2(xc,mc,xu,mu);
        xu=xc-1; mu=mc-1; lee2(xc,mc,xu,mu);
    }
    /*for(k=0;k<x;k++)
    {
        for(i=0;i<m;i++)
            fout<<g[k][i]<<" ";
        fout<<endl;
    }
    fout<<endl<<endl<<endl;
    for(k=0;k<x;k++)
    {
        for(i=0;i<m;i++)
            fout<<h[k][i]<<" ";
        fout<<endl;
    }*/
    for(k=0,cmin=1000000;k<x;k++)
    {
        for(i=0;i<m;i++)
        {
            if(g[k][i]==h[k][i])
            {
                if(g[k][i]<cmin)
                {
                    cmin=g[k][i];
                    k3=k;
                    i3=i;
                }
            }
        }
    }

    fout<<cmin+1<<" "<<k3+1<<" "<<i3+1<<endl;
    return 0;
}