Cod sursa(job #2088122)

Utilizator petru.ciocirlanPetru Ciocirlan petru.ciocirlan Data 14 decembrie 2017 19:42:27
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.21 kb
#include<iostream>
#include<fstream>
#include<queue>
#include<algorithm>
using namespace std;
ifstream f("rj.in");
ofstream g("rj.out");

int n, m, xs, ys, xt, yt;
short int a[101][101], b[101][101], c[101][101];
char sir[101];

int dx[] = {0,0,-1,1,-1,-1,1,1};
int dy[] = {-1,1,0,0,-1,1,-1,1};

queue < pair <int,int> > Q, R;

void Citire()
{
    int i, j;
    f>>n>>m;
    for(i = 0; i <= m+1; ++i)
        a[0][i] = a[n+1][i] = -2;
    for(i = 0; i <= n+1; ++i)
        a[i][0] = a[i][m+1] = -2;
    for(i = 1; i <= n; ++i)
    {
        f.get();
        f.get(sir, 105);
        for(j = 0; j < m; ++j)
        {
            if(sir[j] == 'X') a[i][j+1] = -1;
            else if(sir[j] == 'R')
            {
                xs = i;
                ys = j+1;
            }
            else if(sir[j] == 'J')
            {
                xt = i;
                yt = j+1;
            }
        }
    }
}

void Afisare()
{
    int mn=10010,x,y,i,j;
    x=y=1;
    for(i=1; i<=n; i++)
        for(j=1; j<=m; j++)
            if(b[i][j]==c[i][j] && b[i][j] && c[i][j] && mn > b[i][j])
            {
                mn=b[i][j];
                x=i;
                y=j;
            }
    g<<mn<<' '<<x<<' '<<y<<'\n';
}

void Lee()
{
    int i;
    pair <int,int> p;
    Q.push(make_pair(xs,ys));
    R.push(make_pair(xt,yt));
    b[xs][ys]=1;
    c[xt][yt]=1;
    while(!Q.empty() && !R.empty())
    {
        p = Q.front();
        for(i=0; i<8; i++)
        {
            if(a[p.first+dx[i]][p.second+dy[i]]==0&&b[p.first+dx[i]][p.second+dy[i]]==0)
            {
                Q.push(make_pair(p.first+dx[i],p.second+dy[i]));
                b[p.first+dx[i]][p.second+dy[i]]=b[p.first][p.second]+1;
            }
        }

        p = R.front();
        for(i=0; i<8; i++)
        {
            if(a[p.first+dx[i]][p.second+dy[i]]==0&&c[p.first+dx[i]][p.second+dy[i]]==0)
            {
                R.push(make_pair(p.first+dx[i],p.second+dy[i]));
                c[p.first+dx[i]][p.second+dy[i]]=c[p.first][p.second]+1;
            }
        }

        Q.pop();
        R.pop();
    }
}

int main()
{
    Citire();
    Lee();
    Afisare();
    return 0;
}