Cod sursa(job #2720296)

Utilizator PureIQNicolcea Gelu-Alexandru PureIQ Data 10 martie 2021 18:31:28
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.55 kb
#include <fstream>
#include <array>
#include <queue>
#include <tuple>
#include <algorithm>
#define DAU ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define PLEC cin.close();return 0;
using namespace std;
ifstream cin("rj.in");
ofstream cout("rj.out");
array<array<int,105>,105>a,visited0,visited1;
vector<tuple<int,int,int>>rez;
int ri,rj,ji,jj,n,m,MIN=10000;
int di[8]={0,1,0,-1,-1,1,-1,1};
int dj[8]={1,0,-1,0,-1,1,1,-1};
struct nod
{
    int x,y;
};
int valid(int x,int y)
{
    return x>=1 && x<=n && y>=1 && y<=m;
}
int Bidirectional_BFS()
{
    deque<nod>q0,q1;
    q0.push_back({ri,rj}),q1.push_back({ji,jj});
    visited0[ri][rj]=1,visited1[ji][jj]=1;
    while(!q0.empty() && !q1.empty())
    {
        nod R=q0.front();
        q0.pop_front();
        if(visited1[R.x][R.y]==visited0[R.x][R.y] && visited1[R.x][R.y] && visited1[R.x][R.y]<=MIN)
        {
            rez.push_back(make_tuple(visited0[R.x][R.y],R.x,R.y));
            MIN=visited0[R.x][R.y];
        }
        for(int i=0;i<8;i++)
        {
            int row=R.x+di[i],col=R.y+dj[i];
            if(valid(row,col) && !visited0[row][col] && a[row][col])
            {
                q0.push_back({row,col});
                visited0[row][col]=visited0[R.x][R.y]+1;
            }
        }
        nod J=q1.front();
        q1.pop_front();
        if(visited1[J.x][J.y]==visited0[J.x][J.y] && visited1[J.x][J.y] && visited1[J.x][J.y]<=MIN)
        {
            rez.push_back(make_tuple(visited0[J.x][J.y],J.x,J.y));
            MIN=visited0[J.x][J.y];
        }
        for(int i=0;i<8;i++)
        {
            int row=J.x+di[i],col=J.y+dj[i];
            if(valid(row,col) && !visited1[row][col] && a[row][col])
            {
                q1.push_back({row,col});
                visited1[row][col]=visited1[J.x][J.y]+1;
            }
        }
    }
}

int main()
{
    DAU
    cin>>n>>m,cin.get();
    for(int i=1;i<=n;i++)
    {
        string s;
        getline(cin,s);
        for(int j=0;s[j];j++)
        {
            switch (s[j])
            {
                case ' ':a[i][j+1]=1;
                        break;
                case 'X':a[i][j+1]=0;
                        break;
                case 'J':a[i][j+1]=3,ji=i,jj=j+1;
                        break;
                case 'R':a[i][j+1]=3,ri=i,rj=j+1;
                        break;
            }
        }
    }
    Bidirectional_BFS();
    sort(rez.begin(),rez.end());
    cout<<get<0>(rez[0])<<" "<<get<1>(rez[0])<<" "<<get<2>(rez[0]);
    PLEC
}