Cod sursa(job #2120691)

Utilizator PredaBossPreda Andrei PredaBoss Data 2 februarie 2018 19:33:22
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.33 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("rj.in");
ofstream fout("rj.out");
struct love
{
    int x,y;
};
love r,l;
int i,j,n,m,d;
char a[101];
short dx[8]={1,1,1,0,0,-1,-1,-1};
short dy[8]={1,-1,0,1,-1,1,-1,0};
queue<love>q;
bitset<101>o[101];
short f1[101][101],f2[101][101];
void rezultat()
{d=INT_MAX;
int px,py;
    for(i=1;i<=n;i++){
        for(j=1;j<=m;j++){
            if(max(f1[i][j],f2[i][j])<d && f1[i][j]!=0 && f2[i][j]!=0){
               d=max(f1[i][j],f2[i][j]);
               px=i;
               py=j;
            }
        }
    }
    fout<<d<<" "<<px<<" "<<py;
}
void leej()
{o[l.x][l.y]=1;
f2[l.x][l.y]=1;
    q.push({l.x,l.y});
    while(!q.empty())
    {
        int px=q.front().x;
        int py=q.front().y;
        for(i=0;i<=7;i++){
            if(o[px+dx[i]][py+dy[i]]!=0)
                continue;
            if(f2[px+dx[i]][py+dy[i]]!=0 && f2[px+dx[i]][py+dy[i]]<f2[px][py]+1)
                continue;
            if(px+dx[i]==0 || py+dy[i]==0 || px+dx[i]>n || py+dy[i]>m)
                continue;
            q.push({px+dx[i],py+dy[i]});
            f2[px+dx[i]][py+dy[i]]=f2[px][py]+1;}
        q.pop();
    }
}
void leer()
{o[r.x][r.y]=1;
f1[r.x][r.y]=1;
    q.push({r.x,r.y});
    while(!q.empty())
    {
        int px=q.front().x;
        int py=q.front().y;
        for(i=0;i<=3;i++){
            if(o[px+dx[i]][py+dy[i]]!=0)
                continue;
            if(f1[px+dx[i]][py+dy[i]]!=0 && f1[px+dx[i]][py+dy[i]]<f1[px][py]+1)
                continue;
            if(px+dx[i]==0 || py+dy[i]==0 || px+dx[i]>n || py+dy[i]>m)
                continue;
            q.push({px+dx[i],py+dy[i]});
            f1[px+dx[i]][py+dy[i]]=f1[px][py]+1;}
        q.pop();
    }
    o[r.x][r.y]=0;
}
void cetire()
{
    fin>>n>>m;
    fin.get();
    for(i=1;i<=n;i++){
            fin.get(a,101);
            fin.get();
        for(j=0;j<m;j++){
            if(a[j]=='X'){
                o[i][j+1]=1;
                continue;
            }
            if(a[j]=='R'){
                r.x=i;
                r.y=j+1;
                continue;
            }
            if(a[j]=='J'){
                l.x=i;
                l.y=j+1;
            }
        }
    }
}
int main()
{cetire();
leer();
leej();
rezultat();
    return 0;
}