Cod sursa(job #1890602)

Utilizator TherevengerkingSurani Adrian Therevengerking Data 23 februarie 2017 12:55:44
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.63 kb
#include <iostream>
#include <fstream>
#include <queue>
using namespace std;
ifstream fin("rj.in");
ofstream fout("rj.out");
const int Nmax=100+5;
const int Di[]={-1,-1,-1,0,0,1,1,1};
const int Dj[]={-1,0,1,-1,1,-1,0,1};
const int INF=32000;
int n,m,minim,s1,s2,s3,s4,soli,solj;
queue<pair<short,short> >Q;
bool a[Nmax][Nmax];
short DPR[Nmax][Nmax],DPJ[Nmax][Nmax];
string s;
bool ok(int i,int j)
{
    return i>=1 && i<=n && j<=m && j>=1;
}
void BF(short DP[Nmax][Nmax])
{
    int i,j;
    while(!Q.empty()){
    i=Q.front().first;
    j=Q.front().second;
    Q.pop();
    for(int d=0,ii,jj;d<9;++d)
    {
        ii=i+Di[d];
        jj=j+Dj[d];
        if(ok(ii,jj) && DP[ii][jj]>DP[i][j]+1 && a[ii][jj]==0)
        {
            DP[ii][jj]=DP[i][j]+1;
            Q.push({ii,jj});
        }
    }
    }
}
int main()
{
    fin>>n>>m;
    fin.get();
    for(int i=1;i<=n;++i)
    {
        getline(fin,s);
        //fout<<s<<'\n';
        for(int j=1;j<=m;++j)
        {
            DPR[i][j]=INF;
            DPJ[i][j]=INF;
            if(s[j-1]==' ' or s[j-1]=='\0')a[i][j]=0;
            else if(s[j-1]=='R'){s1=i;s2=j;a[i][j]=0;}
            else if(s[j-1]=='J'){s3=i;s4=j;a[i][j]=0;}
            else a[i][j]=1;
        }
    }
    DPR[s1][s2]=1;
    Q.push({s1,s2});BF(DPR);
    DPJ[s3][s4]=1;
    Q.push({s3,s4});BF(DPJ);
    minim=INF;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
        if(DPJ[i][j]==DPR[i][j] && DPJ[i][j]<minim)
        {
            minim=DPR[i][j];
            soli=i;
            solj=j;
        }
    fout<<minim<<" "<<soli<<" "<<solj;
    return 0;
}