Cod sursa(job #3216107)

Utilizator YuzukyIstrate Andreea Ruxandra Yuzuky Data 15 martie 2024 17:24:56
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.9 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <string>
using namespace std;
ifstream in("rj.in");
ofstream out("rj.out");
const int MAX = 100;
int rom[MAX+1][MAX+1], jul[MAX+1][MAX+1]; //matrice Romea si Julieta
int veclin[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
int veccol[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
int n,m;
struct coord
{
    int lin, col;
};
bool emat (coord vec)
{
    return vec.lin<=n && vec.col<=m && vec.lin>0 && vec.col>0;
}

void leer (coord st) //Lee pt Romeo
{
    queue<coord> q;
    q.push(st);
    rom[st.lin][st.col]=1; //am vizitat-o
    while(!q.empty())
    {
        coord current = q.front();
        q.pop();
        for(int d=0; d<8; ++d)
        {
            coord vec;
            vec.lin = current.lin+veclin[d];
            vec.col = current.col+veccol[d];
            if(emat(vec)==true && rom[vec.lin][vec.col]==0)
            {
                q.push(vec);
                rom[vec.lin][vec.col] = rom[current.lin][current.col]+1;
            }
        }
    }
}

void lee_juliet (coord st) //Lee pt Julieta
{
    queue<coord> q;
    q.push(st);
    jul[st.lin][st.col]=1; //am vizitat-o
    while(!q.empty())
    {
        coord current = q.front();
        q.pop();
        for(int d=0; d<8; ++d)
        {
            coord vec;
            vec.lin = current.lin+veclin[d];
            vec.col = current.col+veccol[d];
            if(emat(vec)==true && jul[vec.lin][vec.col]==0)
            {
                q.push(vec);
                jul[vec.lin][vec.col] = jul[current.lin][current.col]+1;
            }
        }
    }
}
int main()
{
    in>>n>>m;
    char c;
    in.get(c);
    coord romeo, juliet; //coordonatele lui Romeo
    for(int i=0; i<n; ++i)
    {
        string s;
        getline(in, s);
        for(int j=0; j<m; ++j)
        {
            if(s[j]=='R')
            {
                romeo.lin=i+1;
                romeo.col=j+1;
            }
            else if(s[j]=='J')
            {
                juliet.lin=i+1;
                juliet.col=j+1;
            }
            else if(s[j]=='X')
            {
                rom[i+1][j+1]=-1;
                jul[i+1][j+1]=-1;
            }
        }
    }
    leer(romeo);
    lee_juliet(juliet);
    /*cout<<"matricea lui romeo "<<'\n';
    for(int i=1; i<=n; ++i)
    {
        for(int j=1; j<=m; ++j)
            cout<<rom[i][j]<<" ";
        cout<<endl;
    }*/
    int mini=MAX*MAX, linie, coloana;
    for(int i=1; i<=n; ++i)
    {
        for(int j=1; j<=m; ++j)
        {
            int value = rom[i][j];
            if(value==jul[i][j] && value>0)
            {
                if(value<mini)
                {
                    mini=value;
                    linie=i;
                    coloana=j;
                }
            }
        }
    }
    out<<mini<<" "<<linie<<" "<<coloana;
    return 0;
}