Cod sursa(job #1992922)

Utilizator patcasrarespatcas rares danut patcasrares Data 21 iunie 2017 21:21:49
Problema Perle Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.68 kb
#include<fstream>
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
ifstream fin("rj.in");
ofstream fout("rj.out");
int n,m;
char x[105][105];
int a[105][105],b[105][105];
int ju[105][105],r[105][105],tmin=10005,el,ec,jl,jc,rl,rc;
queue<pair<int,int> >q;
int dl[8]={0,0,1,1,1,-1,-1,-1};
int dc[8]={1,-1,-1,0,1,-1,0,1};
void ve1()
{
    int l,c,lnou,cnou;
    while(!q.empty())
    {
        l=q.front().first;
        c=q.front().second;
        q.pop();
        a[l][c]=0;
        for(int i=0;i<8;i++)
        {
            lnou=l+dl[i];
            cnou=c+dc[i];
            if(lnou>0&&lnou<=n&&cnou>=0&&cnou<m&&x[lnou][cnou]==' ')
                if(ju[l][c]+1<ju[lnou][cnou]||ju[lnou][cnou]==0)
                {
                    ju[lnou][cnou]=ju[l][c]+1;
                    if(a[lnou][cnou]==0)
                    {
                        a[lnou][cnou]=1;
                        q.push(make_pair(lnou,cnou));
                    }
                }
        }
    }
}
void ve2()
{
    int l,c,lnou,cnou;
    while(!q.empty())
    {
        l=q.front().first;
        c=q.front().second;
        q.pop();
        b[l][c]=0;
        for(int i=0;i<8;i++)
        {
            lnou=l+dl[i];
            cnou=c+dc[i];
            if(lnou>0&&lnou<=n&&cnou>=0&&cnou<m&&x[lnou][cnou]==' ')
                if(r[l][c]+1<r[lnou][cnou]||r[lnou][cnou]==0)
                {
                    r[lnou][cnou]=r[l][c]+1;
                    if(b[lnou][cnou]==0)
                    {
                        b[lnou][cnou]=1;
                        q.push(make_pair(lnou,cnou));
                    }
                }
        }
    }
}
int main()
{
    fin>>n>>m;
    for(int i=0;i<=n;i++)
    {
        fin.getline(x[i],105);
        if(strlen(x[i])!=m)
        {
            int t=strlen(x[i]);
            for(int j=t;j<m;j++)
                x[i][j]=' ';
            x[i][m]='\0';
        }
    }
    for(int i=1;i<=n;i++)
        for(int j=0;j<m;j++)
            if(x[i][j]=='J')
            {
                jl=i;
                jc=j;
            }
            else
                if(x[i][j]=='R')
                {
                    rl=i;
                    rc=j;
                }
    a[jl][jc]=1;
    ju[jl][jc]=1;
    q.push(make_pair(jl,jc));
    ve1();
    b[rl][rc]=1;
    r[rl][rc]=1;
    q.push(make_pair(rl,rc));
    ve2();
    for(int i=1;i<=n;i++)
        for(int j=0;j<m;j++)
            if(x[i][j]==' '&&r[i][j]==ju[i][j]&&r[i][j]<tmin&&r[i][j])
            {
                tmin=r[i][j];
                el=i;
                ec=j+1;
            }
    fout<<tmin<<' '<<el<<' '<<ec;
}