Cod sursa(job #1180555)

Utilizator SapientiaCHIRILA ADRIAN Sapientia Data 30 aprilie 2014 19:04:20
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 6.07 kb
#include <iostream>
#include <fstream>
#include <queue>
#define Nmax 250
using namespace std;
ifstream f("rj.in");
ofstream g("rj.out");
short int minn=9999,q,t,i,j1,n,m,a[Nmax][Nmax],b[Nmax][Nmax],ro[Nmax][Nmax],ju[Nmax][Nmax];
struct punct {int x,y;};
short int colmin=200;
punct rom,jul;
void reading(short int &n,short int &m)
{
     char c[250];
     int k,j;
     f>>n>>m;
     f.getline(c,250);
     for(k=1;k<=n;++k)
     {
         f.getline(c,250);
         for(j=0;j<=m-1;++j)
          {
              if (c[j]=='X') a[k][j+1]=b[k][j+1]=1;
               else if (c[j]==' ') a[k][j+1]=b[k][j+1]=0;
                else if (c[j]=='R') {a[k][j+1]=b[k][j+1]=0;rom.x=k;rom.y=j+1;}
                  else {a[k][j+1]=b[k][j+1]=0;jul.x=k;jul.y=j+1;}
                  ro[k][j+1]=ju[k][j+1]=0;
          }
     }
     f.close();
}
void leer()
{
   deque<short int>d;
   d.push_front(rom.y);
   d.push_front(rom.x);
   a[rom.y][rom.x]=1;
   while(!d.empty())
   {
       short int xx,yy;
       xx=d.front();d.pop_front();
       yy=d.front();d.pop_front();
       if (xx>1) if (!a[xx-1][yy])
       {
          if (!ro[xx-1][yy])
          {
              ro[xx-1][yy]=ro[xx][yy]+1;
              a[xx-1][yy]=1;
              d.push_back(xx-1);
              d.push_back(yy);
          }
       }
       if (xx<n) if (!a[xx+1][yy])
       {
           if (!ro[xx+1][yy])
           {
               ro[xx+1][yy]=ro[xx][yy]+1;
               a[xx+1][yy]=1;
               d.push_back(xx+1);
               d.push_back(yy);
           }
       }
       if (yy>1) if (!a[xx][yy-1])
       {
           if (!ro[xx][yy-1])
           {
               ro[xx][yy-1]=ro[xx][yy]+1;
               a[xx][yy-1]=1;
               d.push_back(xx);
               d.push_back(yy-1);
           }
       }
       if (yy<m) if (!a[xx][yy+1])
       {
           if (!ro[xx][yy+1])
           {
               ro[xx][yy+1]=ro[xx][yy]+1;
               a[xx][yy+1]=1;
               d.push_back(xx);
               d.push_back(yy+1);
           }
       }
       if (xx<n) if (yy<m) if (!a[xx+1][yy+1])
       {
           if (!ro[xx+1][yy+1])
           {
               ro[xx+1][yy+1]=ro[xx][yy]+1;
               a[xx+1][yy+1]=1;
               d.push_back(xx+1);
               d.push_back(yy+1);
           }
       }
       if (xx>1) if (yy>1) if (!a[xx-1][yy-1])
       {
           if (!ro[xx-1][yy-1])
           {
               ro[xx-1][yy-1]=ro[xx][yy]+1;
               a[xx-1][yy-1]=1;
               d.push_back(xx-1);
               d.push_back(yy-1);
           }
       }
        if (xx<n) if (yy>1) if (!a[xx+1][yy-1])
        {
            if (!ro[xx+1][yy-1])
            {
                ro[xx+1][yy-1]=ro[xx][yy]+1;
                a[xx+1][yy-1]=1;
                d.push_back(xx+1);
                d.push_back(yy-1);
            }
        }
        if (xx>1) if (yy<m) if (!a[xx-1][yy+1])
        {
            if (!ro[xx-1][yy+1])
            {
                ro[xx-1][yy+1]=ro[xx][yy]+1;
                a[xx-1][yy+1]=1;
                d.push_back(xx-1);
                d.push_back(yy+1);
            }
        }
   }
}
void leej()
{
   deque<short int>d;
   d.push_front(jul.y);
   d.push_front(jul.x);
   b[jul.x][jul.y]=1;
   while(!d.empty())
   {
       short int xx,yy;
       xx=d.front();d.pop_front();
       yy=d.front();d.pop_front();
       if (xx>1) if (!b[xx-1][yy])
       {
          if (!ju[xx-1][yy])
          {
              ju[xx-1][yy]=ju[xx][yy]+1;
              b[xx-1][yy]=1;
              d.push_back(xx-1);
              d.push_back(yy);
          }
       }
       if (xx<n) if (!b[xx+1][yy])
       {
           if (!ju[xx+1][yy])
           {
               ju[xx+1][yy]=ju[xx][yy]+1;
               b[xx+1][yy]=1;
               d.push_back(xx+1);
               d.push_back(yy);
           }
       }
       if (yy>1) if (!b[xx][yy-1])
       {
           if (!ju[xx][yy-1])
           {
               ju[xx][yy-1]=ju[xx][yy]+1;
               b[xx][yy-1]=1;
               d.push_back(xx);
               d.push_back(yy-1);
           }
       }
       if (yy<m) if (!b[xx][yy+1])
       {
           if (!ju[xx][yy+1])
           {
               ju[xx][yy+1]=ju[xx][yy]+1;
               b[xx][yy+1]=1;
               d.push_back(xx);
               d.push_back(yy+1);
           }
       }
       if (xx<n) if (yy<m) if (!b[xx+1][yy+1])
       {
           if (!ju[xx+1][yy+1])
           {
               ju[xx+1][yy+1]=ju[xx][yy]+1;
               b[xx+1][yy+1]=1;
               d.push_back(xx+1);
               d.push_back(yy+1);
           }
       }
       if (xx>1) if (yy>1) if (!b[xx-1][yy-1])
       {
           if (!ju[xx-1][yy-1])
           {
               ju[xx-1][yy-1]=ju[xx][yy]+1;
               b[xx-1][yy-1]=1;
               d.push_back(xx-1);
               d.push_back(yy-1);
           }
        }
        if (xx<n) if (yy>1) if (!b[xx+1][yy-1])
        {
            if (!ju[xx+1][yy-1])
            {
                ju[xx+1][yy-1]=ju[xx][yy]+1;
                b[xx+1][yy-1]=1;
                d.push_back(xx+1);
                d.push_back(yy-1);
            }
        }
        if (xx>1) if (yy<m) if (!b[xx-1][yy+1])
        {
            if (!ju[xx-1][yy+1])
            {
                ju[xx-1][yy+1]=ju[xx][yy]+1;
                b[xx-1][yy+1]=1;
                d.push_back(xx-1);
                d.push_back(yy+1);
            }
        }
   }
}
int main()
{
    reading(n,m);
    leer();
    leej();
    for(i=1;i<=n;++i)
    {
        for(j1=1;j1<=m;++j1)
     if ((ro[i][j1]>0) && (ro[i][j1]==ju[i][j1]) && (ro[i][j1]<=minn))
     {
        if (ro[i][j1]==minn && j1<colmin)
        {
            minn=ro[i][j1];
            q=i;t=j1;
            colmin=j1;
        }
        else if (ro[i][j1]<minn)
        {
            minn=ro[i][j1];
            q=i;t=j1;
            colmin=j1;
        }
     }
    }
    g<<minn+1<<" "<<q<<" "<<t;
    g.close();
    return 0;
}