Cod sursa(job #2653673)

Utilizator Teodora1314Teodora Oancea-Negoita Teodora1314 Data 28 septembrie 2020 19:24:13
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.13 kb
#include <iostream>
#include <fstream>
#include <queue>
using namespace std;
queue<pair<int,int> > TEO;
char c[128];
int i,j,n,m,mx,a[105][105],rj[105][105];
int linie,coloana,linienoua,coloananoua,k,x1,x2,y1,y2;
int mn=999999,pozx,pozy;
int const romeo=1;
int const julieta=2;
int dx[8] = {-1,  0, 1, 0, 1, -1, -1, 1};
int dy[8] = { 0, -1, 0, 1, 1, -1, 1, -1};
int main()
{
    ifstream cin ("rj.in");
    ofstream cout ("rj.out");
    cin>>n>>m;
    cin.getline(c+1,103);
    for(i=1;i<=n;i++)
    {
        cin.getline(c+1,103);
        //cout<<(c+1)<<'\n';
        for(j=1;j<=m;j++)
        {

            if(c[j]=='X')
                a[i][j]=1;
            if(c[j]==' ')
                a[i][j]=0;
            if(c[j]=='R')
            {
                x1=i;
                y1=j;
                rj[x1][y1]=romeo;
                TEO.push(make_pair(i,j));
            }
            if(c[j]=='J')
            {
                x2=i;
                y2=j;
                rj[x2][y2]=julieta;
                TEO.push(make_pair(i,j));
            }
        }
    }

    for(j=1; j<=m+1; j++)
    {
        a[0][j]=1;
        a[n+1][j]=1;
    }
    for(i=1;i<=n+1;i++)
    {
        a[i][m+1]=1;
        a[i][0]=1;

    }
    a[x1][y1]=0;
    while(!TEO.empty())
    {
        linie=TEO.front().first;
        coloana=TEO.front().second;
        for(k=0; k<8; k++)
        {
            linienoua=linie+dx[k];
            coloananoua=coloana+dy[k];
            if(linienoua>0 && linienoua<=n && coloananoua>0 && coloananoua<=m && a[linienoua][coloananoua]==0)
            {
                rj[linienoua][coloananoua]=rj[linie][coloana];
                a[linienoua][coloananoua]=a[linie][coloana]+1;
                TEO.push(make_pair(linienoua,coloananoua));
            }
        }
        TEO.pop();
    }
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
            if(rj[i][j]==romeo)
            {
                for(k=0;k<8;k++)
                {
                    int inou=i+dx[k];
                    int jnou=j+dy[k];
                    if(rj[inou][jnou]==julieta && a[inou][jnou]==a[i][j]-1)
                    {
                        if(a[i][j]<mn)
                        {
                            mn=a[i][j];
                            pozx=i;
                            pozy=j;
                        }
                        else if(a[i][j]==mn)
                        {
                            if(i<pozx)
                            {
                                pozx=i;
                                pozy=j;
                            }
                            else if(i==pozx && j<pozy)
                            {
                                pozx=i;
                                pozy=j;
                            }
                        }
                    }
                }
            }
            else if(rj[i][j]==julieta)
            {
                for(k=0;k<8;k++)
                {
                    int inou=i+dx[k];
                    int jnou=j+dy[k];
                    if(rj[inou][jnou]==romeo && a[inou][jnou]==a[i][j]-1)
                    {
                        if(a[i][j]<mn)
                        {
                            mn=a[i][j];
                            pozx=i;
                            pozy=j;
                        }
                        else if(a[i][j]==mn)
                        {
                            if(i<pozx)
                            {
                                pozx=i;
                                pozy=j;
                            }
                            else if(i==pozx && j<pozy)
                            {
                                pozx=i;
                                pozy=j;
                            }
                        }
                    }
                }
            }
        }

    }
    cout<<mn+1<<" "<<pozx<<" "<<pozy;
    // M am gandit ca daca e par timpul in care parcurgi drumul sa impart la 2 si afisez rezultatul. Si daca nu sa luam urmatorul drum.
    return 0;
}