Cod sursa(job #495061)

Utilizator dicu_dariaDaria Dicu dicu_daria Data 23 octombrie 2010 20:36:12
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.73 kb
#include <fstream>
#include <queue>
#include <utility>
#include <cstring>
using namespace std;
int mr[105][105],mj[105][105],rx,ry,jx,jy,x,y,i,j,m,n,l,c,minim;
char car,a[105][105];
queue< pair < int , int > > C;
const int dx[8]={0,1,-1,0,1,-1,1,-1};
const int dy[8]={1,0,0,-1,1,-1,-1,1};
void parcurge_mr()
{
    C.push(make_pair(rx,ry));
    mr[rx][ry]=1;
    while(!C.empty())
    {
        x=C.front().first;
        y=C.front().second;
        C.pop();
        for(i=0;i<8;i++)
        {
            l=x+dx[i]; c=y+dy[i];
            if(a[l][c]!='X' and mr[l][c]==-1) C.push(make_pair(l,c)), mr[l][c]=mr[x][y]+1;
        }


    }

}
void parcurge_mj()
{
    C.push(make_pair(jx,jy));
    mj[jx][jy]=1;
    while(!C.empty())
    {
        x=C.front().first;
        y=C.front().second;
        C.pop();
        for(i=0;i<8;i++)
        {
            l=x+dx[i]; c=y+dy[i];
            if(a[l][c]!='X' and mj[l][c]==-1) C.push(make_pair(l,c)), mj[l][c]=mj[x][y]+1;
        }


    }

}
int main()
{
    ifstream fi("rj.in");
    ofstream fo("rj.out");
    fi>>n>>m;
    fi.get(car);
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
          fi.get(a[i][j]);
          mr[i][j]=-1;
          mj[i][j]=-1;
          if(a[i][j]=='R') rx=i, ry=j;
          if(a[i][j]=='J') jx=i, jy=j;
        }
        fi.get(car);
    }
    for(i=0;i<=n+1;i++) a[i][0]='X', a[i][m+1]='X';
    for(i=0;i<=m+1;i++) a[0][i]='X', a[n+1][i]='X';

    parcurge_mr();
    parcurge_mj();
    minim=int(2e9);
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            if(mr[i][j]==mj[i][j] and mr[i][j]>0 and mr[i][j]<minim) minim=mr[i][j], x=i,y=j;
    fo<<minim<<" "<<x<<" "<<y<<"\n";

    return 0;
}