Cod sursa(job #2132871)

Utilizator Ruxandra985Nanu Ruxandra Laura Ruxandra985 Data 16 februarie 2018 10:30:54
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.02 kb
#include <cstdio>
#include <queue>
#include <algorithm>
#define INF 200000000
using namespace std;
int a[101][101],b[101][101],c[101][101];
queue <pair <int,int> > v;
int di[]={0,0,1,-1,1,1,-1,-1};
int dj[]={-1,1,0,0,1,-1,1,-1};
int main()
{
    FILE *fin=fopen ("rj.in","r");
    FILE *fout=fopen ("rj.out","w");
    int n,m,i,j,ij,jj,ir,jr,d,isol,jsol,mini,iv,jv;
    char ch=0;
    fscanf (fin,"%d%d\n",&n,&m);
    for (i=1;i<=n;i++){
        ch=0;
        for (j=1;j<=m;j++){
            if (ch!='\n')
                ch=fgetc (fin);
            if (ch=='X')
                a[i][j]=-1;
            else a[i][j]=0;
            if (ch=='R'){
                ir=i;
                jr=j;
            }
            else if (ch=='J'){
                ij=i;
                jj=j;
            }
        }
        if (ch!='\n')
            fgetc (fin);
    }
    v.push(make_pair (ir,jr));
    b[ir][jr]=1;
    while (v.size()){
        i=v.front().first;
        j=v.front().second;
        for (d=0;d<8;d++){
            iv=i+di[d];
            jv=j+dj[d];
            if (iv>0 && jv>0 && iv<=n && jv<=m && a[iv][jv]==0 && b[iv][jv]==0){
                b[iv][jv]=1+b[i][j];
                v.push( make_pair (iv,jv));
            }
        }
        v.pop();
    }
    v.push(make_pair (ij,jj));
    c[ij][jj]=1;
    while (v.size()){
        i=v.front().first;
        j=v.front().second;
        for (d=0;d<8;d++){
            iv=i+di[d];
            jv=j+dj[d];
            if (iv>0 && jv>0 && iv<=n && jv<=m && a[iv][jv]==0 && c[iv][jv]==0){
                c[iv][jv]=1+c[i][j];
                v.push( make_pair (iv,jv));
            }
        }
        v.pop();
    }
    mini=INF;
    for (i=1;i<=n;i++){
        for (j=1;j<=m;j++){
            if (a[i][j]==0 && b[i][j]==c[i][j] && b[i][j]<mini && b[i][j]>0){
                mini=b[i][j];
                isol=i;
                jsol=j;
            }
        }
    }
    fprintf (fout,"%d %d %d",mini,isol,jsol);
    return 0;
}