Cod sursa(job #1768586)

Utilizator alisavaAlin Sava alisava Data 1 octombrie 2016 10:57:57
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.16 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("rj.in");
ofstream fout("rj.out");
char a[105][105];
int rom[105][105];
int jul[105][105];
int dl[]={ 1,1,1,-1,-1,-1,0, 0};
int dc[]={-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,j;
    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(jj,ji));
    jul[jj][ji]=0;
    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]=0;
    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;
}