Cod sursa(job #3233875)

Utilizator Sorin_GabrielGabara Sorin Gabriel Sorin_Gabriel Data 5 iunie 2024 11:45:36
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.68 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#define VMAX 105

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

int dir_i[]={-1,-1,0,1,1,1,0,-1};
int dir_j[]={0,1,1,1,0,-1,-1,-1};
pair<int,int> plan[VMAX][VMAX],plan1[VMAX][VMAX];
queue <pair<int,int>> q;


void lee(int i, int j)
{
    int k;
    pair<int,int> x,inlocuitor;
    q.push({i,j});
    plan[i][j].first=1;
    while(!q.empty())
    {
        x=q.front();
        q.pop();
            for(k=0;k<8;k++)
            {
                inlocuitor = plan[x.first+dir_i[k]][x.second+dir_j[k]];
                if(plan[x.first][x.second].second && (inlocuitor.first==0 || inlocuitor.first> plan[x.first][x.second].second +1) )
                    {
                        plan[x.first+dir_i[k]][x.second+dir_j[k]].first = plan[x.first][x.second].second +1;
                        q.push({x.first+dir_i[k] , x.second+dir_j[k]});
                    }
                if(plan[x.first][x.second].first && (inlocuitor.second == 0 || inlocuitor.second > plan[x.first][x.second].first +1) )
                    {
                        plan[x.first+dir_i[k]][x.second+dir_j[k]].second = plan[x.first][x.second].first +1;
                        q.push({x.first+dir_i[k] , x.second+dir_j[k]});
                    }
            }
    }
}

int main()
{
int n,m,i,j,k,ry,rx,jx,jy,t_min=2000000000,x_min,y_min;
char c;
fin>>n>>m;
fin.get(c);

for(i=0;i<n+2;i++)
{
    plan[i][0]=plan[i][m+1]=plan1[i][0]=plan1[i][m+1]={-1,-1};
}
for(i=0;i<m+2;i++)
{
    plan[0][i]=plan[n+1][i]=plan1[0][i]=plan1[n+1][i]={-1,-1};
}

for(i=1;i<=n;i++)
{
    fin.get(c);
    for(j=1;j<=m && c!='\n';j++)
    {
        if(c=='J')
            {
                jx=j;
                jy=i;
            }
        else if(c=='R')
            {
                rx=j;
                ry=i;
            }
        else if(c=='X')
            {
                plan[i][j]={-1,-1};
                plan1[i][j]={-1,-1};
            }
        fin.get(c);
    }
}
lee(ry,rx);
swap(plan,plan1);
lee(jy,jx);


for(i=1;i<=n;i++)
{
    for(j=1;j<=m;j++)
    {
        if(plan[i][j].first == plan1[i][j].first && plan[i][j].first>0 && plan[i][j].first<t_min)
            {
                t_min=plan[i][j].first;
                x_min=i;
                y_min=j;
            }
        else if(plan[i][j].second == plan1[i][j].second && plan[i][j].second>0 && plan[i][j].second<t_min)
            {
                t_min=plan[i][j].second;
                x_min=i;
                y_min=j;
            }
    }
}
fout<<t_min<<" "<<x_min<<" "<<y_min<<'\n';


    return 0;
}