Cod sursa(job #1769313)

Utilizator alisavaAlin Sava alisava Data 2 octombrie 2016 13:02:28
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.17 kb
#include <fstream>
#include <queue>
using namespace std;

ifstream fin("rj.in");
ofstream fout("rj.out");
char a[102][102];
int rom[102][102];
int jul[102][102];
int dl[10]={ 1,1,1,-1,-1,-1,0, 0};
int dc[10]={-1,0,1,-1, 1, 0,1,-1};
int n,m,rj,ri,jj,ji,iint,jint;
queue< pair <int,int> >q;
void Citire()
{
    int i;
    fin>>n>>m;
    fin.get();
    for(i=1;i<=n;i++)
        fin.getline((a[i]+1),105);
}
void Bordare()
{
    int i,j;
    for(i=1;i<=n;i++)
    a[i][0]=a[i][m+1]='X';
     for(j=1;j<=n;j++)
    a[0][j]=a[n+1][j]='X';
}
void preLee()
{
    int i,j;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            {
             jul[i][j]=1000000;
             rom[i][j]=1000000;
             if(a[i][j]=='R') {rj=j;ri=i;}
             if(a[i][j]=='J') {jj=j;ji=i;}

            }
}
void LeeJ()
{
    int i,j,k,x,y;
    q.push(make_pair(ji,jj));
    jul[ji][jj]=1;
    while(!q.empty())
    {
        i=q.front().first;
        j=q.front().second;
        q.pop();
        for(k=0;k<8;k++)
        {
            x=i+dl[k];
            y=j+dc[k];
            if(a[x][y]==' '&&jul[x][y]>=jul[i][j]+1)
            {
                q.push(make_pair(x,y));
                jul[x][y]=jul[i][j]+1;
            }
        }
    }
}
void LeeR()
{
    int i,j,x,y;
    q.push(make_pair(rj,ri));
    rom[rj][ri]=1;
    while(!q.empty())
    {
        i=q.front().first;
        j=q.front().second;
        q.pop();
        for(int k=0;k<8;k++)
        {
            x=i+dl[k];
            y=j+dc[k];
            if(a[x][y]==' '&&rom[x][y]>=rom[i][j]+1)
            {
                q.push(make_pair(x,y));
                rom[x][y]=rom[i][j]+1;
            }
        }
    }
}
void CautLoc()
{
    int minim=1000000,i,j;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
        {
            if(jul[i][j]==rom[i][j]&&jul[i][j]<=minim)
            {
                iint=i;
                jint=j;
                minim=jul[i][j];
            }
        }
    fout<<minim<<" "<<iint<<" "<<jint<<"\n";
}

int main()
{
    Citire();
    Bordare();
    preLee();
    LeeJ();
    LeeR();
    CautLoc();

    return 0;
}