Cod sursa(job #1247804)

Utilizator marian98Horodnic Gheorghe Marian marian98 Data 23 octombrie 2014 22:09:14
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.51 kb
#include<iostream>
#include<fstream>
#include<queue>
using namespace std;
int n,m,A[100][100],Aj[100][100];
queue<pair<int,int> >coada;
queue<pair<int,int> >intalniri;
int di[]={0,-1,-1,-1,0,1,1,1};
int dj[]={-1,-1,0,1,1,1,0,-1};
int ir,jr,ij,jj;
int in[100],ct=0;
void Lee()
{
    int i;
    while(!coada.empty())
    {
        int ic,jc;
        ic=coada.front().first;
        jc=coada.front().second;
        coada.pop();
        for (i=0;i<=7;i++)
        {
            int ci,cj;
            ci=ic+di[i];
            cj=jc+dj[i];
            if (ci>=2 && ci<=n+1 && cj>=1 && cj<=m)
                if (A[ci][cj]==0)
            {
                coada.push(make_pair(ci,cj));
                A[ci][cj]=A[ic][jc]+1;
            }
        }
    }
}
void Leej()
{
    int i;
    while(!coada.empty())
    {
        int ic,jc;
        ic=coada.front().first;
        jc=coada.front().second;
        coada.pop();
        for (i=0;i<=7;i++)
        {
            int ci,cj;
            ci=ic+di[i];
            cj=jc+dj[i];
            if (ci>=2 && ci<=n+1 && cj>=1 && cj<=m)
                if (Aj[ci][cj]==0)
            {
                coada.push(make_pair(ci,cj));
                Aj[ci][cj]=Aj[ic][jc]+1;
            }
        }
    }
}
int main()
{
    ifstream f("rj.in");
    ofstream f1("rj.out");
    f>>n>>m;
    for (int i=1;i<=n+1;i++)
    {
        char c[100];
        f.getline(c,sizeof(c),'\n');
        for (int k=1;k<=m;k++)
        {
            if (c[k-1]=='J') {A[i][k]=0;    ij=i;   jj=k;}
            if (c[k-1]=='R') {A[i][k]=0;    ir=i;   jr=k;}
            if (c[k-1]==' ') A[i][k]=0;
            if (c[k-1]=='X') A[i][k]=-1;
            Aj[i][k]=A[i][k];
        }
    }
    coada.push(make_pair(ir,jr));
    Lee();
    coada.push(make_pair(ij,jj));
    Leej();
    A[ir][jr]=0;
    Aj[ij][jj]=0;
    for (int i=2;i<=n+1;i++)
        for (int j=1;j<=m;j++)
    {
        if (A[i][j]==Aj[i][j] && A[i][j]!=0 && A[i][j]!=-1 && Aj[i][j]!=0 && Aj[i][j]!=-1)
        {
            intalniri.push(make_pair(i,j));
        }
    }
    int contor=1;
    int minim=120,im,jm;
    while(!intalniri.empty())
    {
        if (minim>A[intalniri.front().first][intalniri.front().second])
        {
            minim=A[intalniri.front().first][intalniri.front().second];
            im=intalniri.front().first;
            jm=intalniri.front().second;
        }
        intalniri.pop();
    }
    f1<<im-1<<" "<<jm<<" "<<A[im][jm];
    return 0;
}