Cod sursa(job #2950368)

Utilizator MrPuzzleDespa Fabian Stefan MrPuzzle Data 3 decembrie 2022 15:51:53
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.66 kb
/// Aceasta sursa este pentru problema
/// https://infoarena.ro/problema/rj
/// Punctaj: 100
/// Grupa Medie

#include<fstream>
#include<iostream>
#include<climits>
#include<algorithm>
#include<cstring>
#include<cmath>
#include <vector>
#include <queue>

#define DIM 100
#define INF DIM * DIM + 5

using namespace std;

ifstream f("rj.in");
ofstream g("rj.out");

//ifstream f("in.in");
//ofstream g("out.out");

int n,m;
int r[DIM+5][DIM+5],j[DIM+5][DIM+5];
int rx,ry,jx,jy;

char s[DIM+5];

struct poz{
    int x;
    int y;
    int step;
};

int dx[] = { 1, 1, 1,-1,-1,-1, 0, 0};
int dy[] = { 0, 1,-1, 0, 1,-1, 1,-1};

void lee(int startx,int starty,int a[DIM+5][DIM+5]){

    queue <poz> q;
    q.push({startx,starty,0});

    while(!q.empty()){

        int x = q.front().x;
        int y = q.front().y;
        int step = q.front().step;

        for(int i=0;i<=7;i++){
            int newx = x + dx[i];
            int newy = y + dy[i];
            int newstep = step+1;

            if(1<=newx && newx<=n &&
               1<=newy && newy<=m &&
               a[newx][newy] == 0){

                a[newx][newy] = newstep;
                q.push({newx,newy,newstep});
            }
        }

        q.pop();
    }
}

int main(){

    f>>n>>m;
    for(int i=1;i<=n;i++){
        f.get();
        f.get(s+1,DIM+5);
        for(int i2=1;i2<=m;i2++){
            if(s[i2] == ' '){
                r[i][i2] = 0;
                j[i][i2] = 0;
            }else if(s[i2] == 'X'){
                r[i][i2] = -1;
                j[i][i2] = -1;
            }else if(s[i2] == 'R'){
                r[i][i2] = -1;
                j[i][i2] = -1;

                rx = i;
                ry = i2;
            }if(s[i2] == 'J'){
                r[i][i2] = -1;
                j[i][i2] = -1;

                jx = i;
                jy = i2;
            }
        }
    }

    lee(rx,ry,r);
    lee(jx,jy,j);

    /*for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cout<<r[i][j]<<" ";
        }
        cout<<'\n';
    }
    cout<<'\n'<<'\n';
    for(int i=1;i<=n;i++){
        for(int jj=1;jj<=m;jj++){
            cout<<j[i][jj]<<" ";
        }
        cout<<'\n';
    }*/

    int mini = INF,minix,miniy;
    for(int i=1;i<=n;i++){
        for(int i2=1;i2<=m;i2++){
            if(r[i][i2] == j[i][i2] &&
                r[i][i2] > 0 &&
                r[i][i2] < mini){

                mini = r[i][i2];
                minix = i;
                miniy = i2;
            }
        }
    }

    g<<mini<<" "<<minix<<" "<<miniy;

    f.close();
    g.close();
    return 0;
}