Cod sursa(job #1995319)

Utilizator IsacLucianIsac Lucian IsacLucian Data 27 iunie 2017 16:24:53
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.33 kb
#include <bits/stdc++.h>
#define oo 1000000

using namespace std;

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

char aux[102][102];
int a[102][102],b[102][102],n,m,xr,yr,xj,yj;
int dx[]={-1,-1,-1,0,1,1,1,0};
int dy[]={-1,0,1,1,1,0,-1,-1};
queue<pair<int,int> >q;

void Citire()
{
    int i,j;
    fin>>n>>m;

    i=0;
    while(fin.getline(aux[i],101))
        i++;

    for(i=1;i<=n;i++)
    {
        for(j=0;j<m;j++)
        {
            if(aux[i][j]=='R')
            {
                xr=i;
                yr=j;
            }
            else if(aux[i][j]=='J')
            {
                xj=i;
                yj=j;
            }
        }
    }

}

void Initializare()
{
    int i,j;
    for(i=1;i<=n;i++)
        for(j=0;j<m;j++)
            a[i][j]=b[i][j]=oo;
}

inline bool Verificare(int i,int j)
{
    if(i>=1 && i<=n && j>=0 && j<m)
        return true;
    return false;
}

void Lee_R()
{
    int i,j,x,y,k;
    b[xr][yr]=1;
    q.push(make_pair(xr,yr));
    while(!q.empty())
    {
        i=q.front().first;
        j=q.front().second;
        q.pop();
        for(k=0;k<8;k++)
        {
            x=i+dx[k];
            y=j+dy[k];
            if(Verificare(x,y) && aux[x][y]!='X' && b[x][y]>b[i][j]+1)
            {
                b[x][y]=b[i][j]+1;
                q.push(make_pair(x,y));
            }
        }
    }
}

void Lee_J()
{
    int i,j,x,y,k;
    a[xj][yj]=1;
    q.push(make_pair(xj,yj));
    while(!q.empty())
    {
        i=q.front().first;
        j=q.front().second;
        q.pop();
        for(k=0;k<8;k++)
        {
            x=i+dx[k];
            y=j+dy[k];
            if(aux[x][y]!='X' && Verificare(x,y) && a[x][y]>a[i][j]+1)
            {
                a[x][y]=a[i][j]+1;
                q.push(make_pair(x,y));
            }
        }
    }
}

void Rezolva()
{
    int i,j,dist,x,y;
    dist=LONG_MAX;
    for(i=1;i<=n;i++)
        for(j=0;j<m;j++)
            if(a[i][j]!=oo && b[i][j]<dist && a[i][j]==b[i][j])
            {
                x=i;
                y=j+1;
                dist=a[i][j];
            }
    fout<<dist<<" "<<x<<" "<<y<<"\n";

}
int main()
{
    Citire();
    Initializare();
    Lee_J();
    Lee_R();
    Rezolva();
    fin.close();
    fout.close();
    return 0;
}