Cod sursa(job #2623913)

Utilizator GligarEsterabadeyan Hadi Gligar Data 4 iunie 2020 09:43:29
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.52 kb
#include <fstream>
#include <queue>

using namespace std;

ifstream fin("rj.in");
ofstream fout("rj.out");

const int nd=8;
const int dx[nd]={1,-1,0,0,1,1,-1,-1}, dy[nd]={0,0,1,-1,-1,1,-1,1};
const int nmax=100,mmax=100;

int v[nmax+2][mmax+2];
int vj[nmax+2][mmax+2];

struct str{
    int x,y;
};

queue <str> q;

int main(){
    int n,m;
    fin>>n>>m;
    for(int i=0;i<=n+1;++i){
        v[i][0]=-1;
        v[i][m+1]=-1;
    }
    for(int j=1;j<=m;++j){
        v[0][j]=-1;
        v[n+1][j]=-1;
    }
    string z;
    getline(fin,z);
    str jp;
    for(int i=1;i<=n;i++){
        getline(fin,z);
        for(int j=1;j<=m&&j<=int(z.size());++j){
            if(z[j-1]=='X'){
                v[i][j]=-1;
            }else if(z[j-1]=='R'){
                v[i][j]=1;
                str aux;
                aux.x=i;
                aux.y=j;
                q.push(aux);
            }else if(z[j-1]=='J'){
                jp.x=i;
                jp.y=j;
            }
        }
    }
    while(q.empty()==0){
        int x=q.front().x, y=q.front().y;
        q.pop();
        for(int i=0;i<nd;i++){
            int xn=x+dx[i], yn=y+dy[i];
            if(v[xn][yn]==0){
               v[xn][yn]=v[x][y]+1;
               str aux;
               aux.x=xn;
               aux.y=yn;
               q.push(aux);
            }
        }
    }
        /*for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            fout<<v[i][j]<<" ";
        }
        fout<<"\n";
    }*/
    for(int i=0;i<=n+1;++i){
        for(int j=0;j<=m+1;++j){
            if(v[i][j]==-1){
                vj[i][j]=-1;
            }
        }
    }
    vj[jp.x][jp.y]=1;
    q.push(jp);
    while(q.empty()==0){
        int x=q.front().x, y=q.front().y;
        q.pop();
        for(int i=0;i<nd;i++){
            int xn=x+dx[i], yn=y+dy[i];
            if(vj[xn][yn]==0){
               vj[xn][yn]=vj[x][y]+1;
               str aux;
               aux.x=xn;
               aux.y=yn;
               q.push(aux);
            }
        }
    }
    /*for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            fout<<vj[i][j]<<" ";
        }
        fout<<"\n";
    }*/
    int sol=n*m,solx=-1,soly=-1;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            if(v[i][j]==vj[i][j]&&v[i][j]>0&&v[i][j]<sol){
                sol=v[i][j];
                solx=i;
                soly=j;
            }
        }
    }
    fout<<sol<<" "<<solx<<" "<<soly<<"\n";
    return 0;
}