Cod sursa(job #1290009)

Utilizator ionut98Bejenariu Ionut Daniel ionut98 Data 10 decembrie 2014 18:20:05
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.41 kb
#include<fstream>
#include<cstring>
#include<deque>
using namespace std;
ifstream f("rj.in");
ofstream g("rj.out");
int a[102][102],b[102][102],xr,yr,xj,yj,i,j,n,m,fin,ln,xfin,yfin;
const int dx[]={-1,-1,0,1,1,1,0,-1};
const int dy[]={0,1,1,1,0,-1,-1,-1};
char x[102];
void citire()
{
    f>>n>>m;
    f.getline(x,102);
    while(!f.eof())
    {
        ln++;
        f.getline(x,102);
        for(i=0;i<m;i++)
        {
            if(x[i]=='X')
            a[ln][i+1]=b[ln][i+1]=-1;
            else if(x[i]=='R')
            {
                xr=ln;
                yr=i+1;
            }
            else if(x[i]=='J')
            {
                xj=ln;
                yj=i+1;
            }
        }
    }
}
void bordare()
{
    for(i=0;i<=n+1;i++)
      a[i][0]=b[i][0]=b[i][m+1]=a[i][m+1]=-1;
    for(j=1;j<=m;j++)
      a[0][j]=b[0][j]=a[n+1][j]=b[n+1][j]=-1;
}
void leer(int xr,int yr)
{
    typedef pair<int,int> celula;
    deque <celula> q;
    int xx,yy,x,y,i;
    a[xr][yr]=1;
    q.push_back(make_pair(xr,yr));
    while(!q.empty())
    {
        x=q.front().first;
        y=q.front().second;
        q.pop_front();
        for(i=0;i<8;i++)
        {
            xx=x+dx[i];
            yy=y+dy[i];
            if(a[xx][yy]==0)
            {
                a[xx][yy]=a[x][y]+1;
                q.push_back(make_pair(xx,yy));
            }
        }
    }
}
void leej(int xj,int yj)
{
    typedef pair<int,int> celul;
    deque <celul> q;
    int xx,yy,x,y,i;
    b[xj][yj]=1;
    q.push_back(make_pair(xj,yj));
    while(!q.empty())
    {
        x=q.front().first;
        y=q.front().second;
        q.pop_front();
        for(i=0;i<8;i++)
        {
            xx=x+dx[i];
            yy=y+dy[i];
            if(b[xx][yy]==0)
            {
                b[xx][yy]=b[x][y]+1;
                q.push_back(make_pair(xx,yy));
            }
        }
    }
}
void comparare()
{
    fin=1001000;
    for(i=1;i<=n;i++)
      for(j=1;j<=m;j++)
        if(a[i][j]==b[i][j]&&a[i][j]>0&&a[i][j]<fin)
        {
            fin=a[i][j];
            xfin=i;
            yfin=j;
        }
}
int main()
{
    citire();
    bordare();
    leer(xr,yr);
    leej(xj,yj);
    comparare();
    /*for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        g<<b[i][j]<<" ";
        g<<"\n";
    }*/
    g<<fin<<" "<<xfin<<" "<<yfin;
    return 0;
}