Cod sursa(job #1014136)

Utilizator Tuddy18Tolciu Tudor Tuddy18 Data 22 octombrie 2013 09:48:55
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 6.33 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <climits>
#include <string>
using namespace std;
ifstream fin("rj.in");
ofstream fout("rj.out");
char a;
string s;
int n,m,oras[105][105],r[105][105],j[105][105],i,k,h,xr,yr,xj,yj,xc,yc,xu,yu,minim=INT_MAX,xmin,ymin;
queue <int> xro,yro,xju,yju;
void afisare(int a[105][105])
{
    for (int i=0;i<=n;i++)
    {
        for (int j=0;j<=m;j++)
            cout << a[i][j] << ' ';
        cout << endl;
    }
}
int main()
{
    fin>>n>>m;
    for(i=0;i<=n+1;i++)
        r[i][0]=j[i][0]=oras[i][0]=n*m+1;
   for(i=1;i<=m+1;i++)
        r[0][i]=j[0][i]=oras[0][i]=n*m+1;
getline(fin,s);
for(i=1;i<=n;i++)
for(k=1;k<=m;k++)
       r[i][k]=j[i][k]=n*m+1;
  for(i=1;i<=n;i++)
  {
      getline(fin,s);
      for(k=0;k<=m-1;k++)
      {
          if(s[k]==' ')
            oras[i][k+1]=0;
          if(s[k]=='X')
            oras[i][k+1]=n*m+1;
          if(s[k]=='R')
        {
            xr=i;
            yr=k+1;
        oras[i][k+1]=0;
        }
        if(s[k]=='J')
        {
            xj=i;
            yj=k+1;
        oras[i][k+1]=0;
        }
      }
      cout<<xr<<" "<<yr<<" "<<xj<<" "<<yj<<endl;
  }

// ROMEO .......................................................................
   xro.push(xr);
   yro.push(yr);
   r[xr][yr]=1;
   while(xro.empty()==0)
   {
       xc=xro.front();xro.pop();
       yc=yro.front();yro.pop();
       //1 diagonala dreapta sus
       if(oras[xc-1][yc+1]==0)
       {if(r[xc-1][yc+1]>r[xc][yc]+1)
            {
                r[xc-1][yc+1]=r[xc][yc]+1;
                xro.push(xc-1);
                yro.push(yc+1);
            }}
        //2 orizontala dreapta
       if(oras[xc][yc+1]==0)
       {if(r[xc][yc+1]>r[xc][yc]+1)
            {
                r[xc][yc+1]=r[xc][yc]+1;
                xro.push(xc);
                yro.push(yc+1);
            }}
        //3 diagonala dreapta jos
        if(oras[xc+1][yc+1]==0)
       {if(r[xc+1][yc+1]>r[xc][yc]+1)
            {
                r[xc+1][yc+1]=r[xc][yc]+1;
                xro.push(xc+1);
                yro.push(yc+1);
            }}
                    //4 verticala jos
       if(oras[xc+1][yc]==0)
       {if(r[xc+1][yc]>r[xc][yc]+1)
            {
                r[xc+1][yc]=r[xc][yc]+1;
                xro.push(xc+1);
                yro.push(yc);
            }}
        //5 diagonala stanga jos
       if(oras[xc+1][yc-1]==0)
       {if(r[xc+1][yc-1]>r[xc][yc]+1)

              {
                r[xc+1][yc-1]=r[xc][yc]+1;
                xro.push(xc+1);
                yro.push(yc-1);
            }}
        //6 orizontala stanga
       if(oras[xc][yc-1]==0)
       if(r[xc][yc-1]>r[xc][yc]+1)
            {
                r[xc][yc-1]=r[xc][yc]+1;
                xro.push(xc);
                yro.push(yc-1);
            }
        //7 diagonala stanga sus
       if(oras[xc-1][yc-1]==0)
       {if(r[xc-1][yc-1]>r[xc][yc]+1)
            {
                r[xc-1][yc-1]=r[xc][yc]+1;
                xro.push(xc-1);
                yro.push(yc-1);
            }}
        //8 verticala sus
        if(oras[xc-1][yc]==0)
       {
           if(r[xc-1][yc]>r[xc][yc]+1)
            {
                r[xc-1][yc]=r[xc][yc]+1;
                xro.push(xc-1);
                yro.push(yc);
            }}
   }


//JULIETA.  ...........................................................................................................
    xju.push(xj);
   yju.push(yj);
      j[xj][yj]=1;

   while(xju.empty()==0)
   {
       xc=xju.front();xju.pop();
       yc=yju.front();yju.pop();
       //1 diagonala dreapta sus
       if(oras[xc-1][yc+1]==0)
       if(j[xc-1][yc+1]>j[xc][yc]+1)
            {
                j[xc-1][yc+1]=j[xc][yc]+1;
                xju.push(xc-1);
                yju.push(yc+1);
            }
        //2 orizontala dreapta
       if(oras[xc][yc+1]==0)
       if(j[xc][yc+1]>j[xc][yc]+1)
            {
                j[xc][yc+1]=j[xc][yc]+1;
                xju.push(xc);
                yju.push(yc+1);
            }
        //3 diagonala dreapta jos
        if(oras[xc+1][yc+1]==0)
       if(j[xc+1][yc+1]>j[xc][yc]+1)
            {
                j[xc+1][yc+1]=j[xc][yc]+1;
                xju.push(xc+1);
                yju.push(yc+1);
            }
        //4 verticala jos
       if(oras[xc+1][yc]==0)
       if(j[xc+1][yc]>j[xc][yc]+1)
            {
                j[xc+1][yc]=j[xc][yc]+1;
                xju.push(xc+1);
                yju.push(yc);
            }
        //5 diagonala stanga jos
       if(oras[xc+1][yc-1]==0)
       if(j[xc+1][yc-1]>j[xc][yc]+1)
            {
                j[xc+1][yc-1]=j[xc][yc]+1;
                xju.push(xc+1);
                yju.push(yc-1);
            }
        //6 orizontala stanga
       if(oras[xc][yc-1]==0)
       if(j[xc][yc-1]>j[xc][yc]+1)
            {
                j[xc][yc-1]=j[xc][yc]+1;
                xju.push(xc);
                yju.push(yc-1);
            }
        //7 diagonala stanga sus
       if(oras[xc-1][yc-1]==0)
       if(j[xc-1][yc-1]>j[xc][yc]+1)
            {
                j[xc-1][yc-1]=j[xc][yc]+1;
                xju.push(xc-1);
                yju.push(yc-1);
            }
        //8 verticala sus
        if(oras[xc-1][yc]==0)
        if(j[xc-1][yc]>j[xc][yc]+1)
            {
                j[xc-1][yc]=j[xc][yc]+1;
                xju.push(xc-1);
                yju.push(yc);
            }
   }
    afisare(r);
    cout << endl;
    afisare(j);
   for(i=0;i<=n;i++)
      {for(k=0;k<=m;k++)

        for(i=1;i<=n;i++)
        for(k=1;k<=m;k++)
        {
            if(r[i][k]==j[i][k])
             {
                 if(r[i][k]<minim)
                {
                        minim=r[i][k];
                        xmin=i;
                        ymin=k;
                }
                if(r[i][k]==minim)
                {
                    if(i<xmin)
                    {
                        xmin=i;
                        ymin=k;
                    }
                    if(i==xmin)
                    {
                        if(k<ymin)
                            ymin=k;
                    }
                }

            }


        }
      }
        fout<<minim<<' '<<xmin<<' '<<ymin;
        return 0;}