Cod sursa(job #2131935)

Utilizator PredaBossPreda Andrei PredaBoss Data 15 februarie 2018 10:15:04
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.17 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("rj.in");
ofstream fout("rj.out");
struct poz
{
    int x,y;
};
poz r,l;
char a[102];
bool f[105][105];
int R[102][102],J[102][102];
int dx[8]={1,1,1,0,0,-1,-1,-1};
int dy[8]={1,-1,0,1,-1,1,-1,0};
int n,m,i,j,k,p,c;
queue<poz>q1,q2;
int ok(int p1,int p2)
{
    return(p1>0 && p2>0 && p1<=n && p2<=m);
}
void raspuns()
{int mx=INT_MAX;
    for(i=1;i<=n;i++){
        for(j=1;j<=m;j++){
                if(R[i][j]>0 && J[i][j]>0){
            R[i][j]=max(R[i][j],J[i][j]);
            if(R[i][j]<mx && R[i][j]>0){
                mx=R[i][j];
                r.x=i;
                r.y=j;
            }
        }}
    }
    fout<<mx<<" "<<r.x<<" "<<r.y;
}
void julieta()
{q2.push({l.x,l.y});
f[l.x][l.y]=1;
    while(!q2.empty()){
        int ii=q2.front().x;
        int jj=q2.front().y;
        if(ii==r.x && jj==r.y)
            break;
        q2.pop();
        for(i=0;i<8;i++){
            int ix=ii+dx[i];
            int jy=jj+dy[i];
        if(f[ix][jy]==0 && (J[ix][jy]==0 || J[ii][jj]+1<R[ix][jy])&& ok(ix,jy)){
            q2.push({ix,jy});
            J[ix][jy]=J[ii][jj]+1;
        }}}
}
void romeo()
{q1.push({r.x,r.y});
f[r.x][r.y]=1;
    while(!q1.empty()){
        int ii=q1.front().x;
        int jj=q1.front().y;
           if(ii==l.x && jj==l.y)
            break;
        q1.pop();
        for(i=0;i<8;i++){
            int ix=ii+dx[i];
            int jy=jj+dy[i];
        if(f[ix][jy]==0 && (R[ix][jy]==0 || R[ii][jj]+1<R[ix][jy])&& ok(ix,jy)){
            q1.push({ix,jy});
            R[ix][jy]=R[ii][jj]+1;
        }}}
}
void cetire()
{
    fin>>n>>m;
    fin.get();
    for(i=1;i<=n;i++){
        fin.get(a,102);
        fin.get();
        for(j=1;j<=m;j++){
            if(a[j-1]=='R'){
                r.x=i;
                r.y=j;
                continue;
                }
            if(a[j-1]=='J'){
                l.x=i;
                l.y=j;
                continue;
            }
            if(a[j-1]=='X')
                f[i][j]=1;
        }
    }
}
int main()
{cetire();
romeo();
julieta();
raspuns();
    return 0;
}