Cod sursa(job #2205768)

Utilizator roxana.aeleneiAelenei Roxana roxana.aelenei Data 20 mai 2018 11:15:02
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.46 kb
#include <bits/stdc++.h>
using namespace std;
void Bordare(pair<int,int> a[105][105], int n, int m)
{
    for(int i=0; i<=n+1; i++)
    {
        a[i][0] = make_pair(-1,-1);
        a[i][m+1] = make_pair(-1,-1);
    }
    for(int j=0; j<=m+1; j++)
    {
        a[0][j] = make_pair(-1,-1);
        a[n+1][j] = make_pair(-1,-1);
    }
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            a[i][j] = make_pair(0,0);
}

void leeR(pair<int,int> a[105][105], pair<int,int> start)
{
    int ox[]={ 1, 0,-1, 0, 1,-1, 1,-1};
    int oy[]={ 0, 1, 0,-1,-1, 1, 1,-1};
    queue <pair<int,int> > q;
    q.push(start);
    while(!q.empty())
    {
        pair <int,int> u = q.front();
        q.pop();
        for(int k = 0; k < 8; k++)
        {
            pair<int,int> v;
            v.first = u.first + ox[k];
            v.second = u.second + oy[k];
            if(!a[v.first][v.second].first)
            {
                a[v.first][v.second].first = a[u.first][u.second].first + 1;
                q.push(v);
            }
        }
    }
}

void leeJ(pair<int,int> a[105][105], pair<int, int> start, pair<int,pair<int,int> >  &sol)
{
    int ox[]={ 1, 0,-1, 0, 1,-1, 1,-1};
    int oy[]={ 0, 1, 0,-1,-1, 1, 1,-1};
    queue <pair<int,int> > q;
    q.push(start);
    while(!q.empty())
    {
        pair <int,int> u = q.front();
        q.pop();
        for(int k = 0; k < 8; k++)
        {
            pair<int,int> v;
            v.first = u.first + ox[k];
            v.second = u.second + oy[k];
            if(!a[v.first][v.second].second)
            {
                a[v.first][v.second].second = a[u.first][u.second].second + 1;
                if(a[v.first][v.second].first == a[v.first][v.second].second){
                        if(a[v.first][v.second].first < sol.first)
                            sol = make_pair(a[v.first][v.second].first, make_pair(v.first,v.second));
                        else if(a[v.first][v.second].first == sol.first)
                        {
                            if(v.first < sol.second.first)
                                sol = make_pair(a[v.first][v.second].first, make_pair(v.first,v.second));
                            else if( v.first == sol.second.first && v.second < sol.second.second)
                                sol = make_pair(a[v.first][v.second].first, make_pair(v.first,v.second));

                        }
                }
                q.push(v);
            }
        }
    }
}

int main ()
{
    ifstream in("rj.in");
    ofstream out("rj.out");
    pair<int,int> pozj, pozr;
    pair<int,int> a[105][105];
    int n,m;
    string row;
    pair<int,pair<int,int> >  sol;
    in>>n>>m;
    getline(in,row);
    Bordare(a,n,m);
    for(int i=1; i<=n; i++)
    {
        getline(in,row);
        for(int j=0; j<row.size(); j++)
        {
            if(row[j] == 'R')
            {
                pozr.first = i;
                pozr.second = j+1;
            }
            if(row[j] == 'J')
            {
                pozj.first = i;
                pozj.second = j+1;
            }
            if(row[j] == 'X')
                {
                    a[i][j+1].first = -1;
                    a[i][j+1].second = -1;
                }
        }
    }
    leeR(a,pozr);
    sol = make_pair(10000, make_pair(0,0));
    leeJ(a,pozj,sol);
    out<<sol.first + 1<<" "<<sol.second.first<<" "<<sol.second.second<<'\n';
    return 0;
}