Cod sursa(job #878437)

Utilizator ard_procesoareLupicu ard_procesoare Data 14 februarie 2013 15:03:57
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.19 kb
#include <fstream>
#include <queue>
using namespace std;
ifstream fin("rj.in");
ofstream fout("rj.out");
#define NMAX 105
char sir[NMAX];
int n,x1,x2,y1,y2,m,v[NMAX][NMAX],d1[NMAX][NMAX],d2[NMAX][NMAX];
queue <int> qx,qy,qval;
void read()
{
    fin>>n>>m;
    fin.getline(sir,0);
    for(int i=1;i<=n;i++)
    {
        fin.getline(sir,m+3);
        for(int j=0;j<=m;j++)
        {
            if(sir[j]=='X')
            {
                v[i][j+1]=1;
                continue;
            }
            if(sir[j]=='R')
            {
                x1=i;
                y1=j+1;
                continue;
            }
            if(sir[j]=='J')
            {
                x2=i;
                y2=j+1;
            }
        }
    }
}
void tipar(int v[NMAX][NMAX])
{
    int i,j;
    for(i=0;i<=n+1;i++)
    {
        for(j=0;j<=m+1;j++)
            fout<<v[i][j]<<" ";
        fout<<"\n";
    }
    fout<<"\n------------\n";
}
void bordeaza()
{
    int i,j;
    j=n;
    if(m>j) j=m;
    for(i=0;i<=j+1;i++)
        v[0][i]=v[i][0]=v[n+1][i]=v[i][m+1]=1;
}
void baga(int x,int y,int d[NMAX][NMAX],int val)
{
    if(v[x][y]==1 || d[x][y] ) return ;
    d[x][y]=val;
    qx.push(x);
    qy.push(y);
    qval.push(val);

}
void bfs(int x,int y,int d[NMAX][NMAX])
{
    qx.push(x);
    qy.push(y);
    qval.push(1);
    d[x][y]=1;
    int a,b,c;
    while(!qx.empty())
    {
        a=qx.front();
        b=qy.front();
        c=qval.front() + 1;
        qx.pop();
        qy.pop();
        qval.pop();
        baga(a+1,b,d,c);
        baga(a-1,b,d,c);
        baga(a+1,b+1,d,c);
        baga(a+1,b-1,d,c);
        baga(a-1,b+1,d,c);
        baga(a-1,b-1,d,c);
        baga(a,b+1,d,c);
        baga(a,b-1,d,c);
    }
}
void sol()
{
    int i,j;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            if(d1[i][j]==d2[i][j] && d1[i][j])
            {
                fout<<d1[i][j]<<" "<<i<<" "<<j;
                return;
            }
}
int main()
{
    read();
    bordeaza();
    bfs(x1,y1,d1);
    bfs(x2,y2,d2);
    sol();
   // tipar(v);
  //  tipar(d1);
  //  tipar(d2);
  //  fout<<x1<<" "<<y1<<" "<<x2<<" "<<y2;
}