Cod sursa(job #1469992)

Utilizator radiogard1999Dragoi Andrei radiogard1999 Data 10 august 2015 09:50:27
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.21 kb
#include <fstream>
#include <queue>
using namespace std;
ifstream fin("rj.in");
ofstream fout("rj.out");

queue < pair<int,int> > q;

char a[102][102];
int n,m,b[102][102],c[102][102];
int xr,yr,xj,yj;
int dx[]={0, 0,1,-1,-1, 1,-1,1};
int dy[]={1,-1,0, 0, 1,-1,-1,1};

void Bordare()
{
    int i;
    for(i=0;i<=n+1;i++)
        a[i][0]=a[i][m+1]='X';
    for(i=0;i<=m+1;i++)
        a[0][i]=a[n+1][i]='X';
}

void Cautare()
{
    int i,j;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
    {
        b[i][j]=c[i][j]=100000;
        if(a[i][j]=='R')
            {
                xr=i;
                yr=j;
            }
         if(a[i][j]=='J')
            {
                xj=i;
                yj=j;
            }
    }
}

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

}

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

}

void Citire()
{
    int i,j;
    fin>>n>>m;
    fin.get();
    for(i=1;i<=n;i++)
        fin.getline(a[i]+1,101);
}


void Afisare()
{
    int i,j,minim=100000;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            if(b[i][j]==c[i][j]&&minim>b[i][j])
        {
            xr=i;
            yr=j;
            minim=b[i][j];
        }
    fout<<minim<<" "<<xr<<" "<<yr<<endl;
    fout.close();
}

int main()
{
    Citire();
    Bordare();
    Cautare();
    Leej();
    Leer();
    Afisare();
    return 0;
}