Cod sursa(job #232137)

Utilizator stocarulCosmin-Mihai Tutunaru stocarul Data 14 decembrie 2008 19:51:48
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.45 kb
#include<fstream.h>
fstream in,out;
char car[120];
int a[102][102],b[102][102];
int i,j,m,n;
void main(void)
{
int julieta[4],ok=1;
int x1[1000],x2[1000],y1[1000],y2[1000],x,y;
in.open("rj.in",ios::in);
in>>n>>m;
in.get();
for(i=1;i<=n;i++)
  {
  in.getline(car,m+2,'\n');
  //in.get();
  for(j=0;j<=m-1;j++)
    {
    if(car[j]=='X')
      {
      a[i][j+1]=-1;
      b[i][j+1]=-1;
      }
    else if(car[j]=='R')
      {
      a[i][j+1]=0;
      b[i][j+1]=1000;
      x1[1]=i;
      y1[1]=j+1;
      }
    else if(car[j]=='J')
      {
      a[i][j+1]=1000;
      b[i][j+1]=0;
      julieta[1]=i;
      julieta[2]=j+1;
      }
    else
      {
      a[i][j+1]=1000;
      b[i][j+1]=1000;
      }
    }
  }
in.close();

j=1;
ok=1;
while(ok==1)
  {
  ok=0;
  x=j;
  j=0;
  for(i=1;i<=x;i++)
    {
    if(x1[i]+1<=n && a[x1[i]+1][y1[i]]!=-1 && a[x1[i]][y1[i]]+1<a[x1[i]+1][y1[i]])
      {
      ok=1;
      // merge in jos
      a[x1[i]+1][y1[i]] = a[x1[i]][y1[i]]+1;
      j++;
      x2[j] = x1[i]+1;
      y2[j] = y1[i];
      }

    if(x1[i]-1>=1 && a[x1[i]-1][y1[i]]!=-1 && a[x1[i]][y1[i]]+1<a[x1[i]-1][y1[i]])
      {
      ok=1;
      // merge in sus
      a[x1[i]-1][y1[i]] = a[x1[i]][y1[i]]+1;
      j++;
      x2[j] = x1[i]-1;
      y2[j] = y1[i];
      }

    if(y1[i]+1<=m && a[x1[i]][y1[i]+1]!=-1 && a[x1[i]][y1[i]]+1<a[x1[i]][y1[i]+1])
      {
      ok=1;
      // merge la dreapta
      a[x1[i]][y1[i]+1] = a[x1[i]][y1[i]]+1;
      j++;
      x2[j] = x1[i];
      y2[j] = y1[i]+1;
      }

    if(y1[i]-1>=0 && a[x1[i]][y1[i]-1]!=-1 && a[x1[i]][y1[i]]+1<a[x1[i]][y1[i]-1])
      {
      ok=1;
      // merge la stanga
      a[x1[i]][y1[i]-1] = a[x1[i]][y1[i]]+1;
      j++;
      x2[j] = x1[i];
      y2[j] = y1[i]-1;
      }

    if(x1[i]+1<=n && y1[i]+1<=m && a[x1[i]+1][y1[i]+1]!=-1 && a[x1[i]][y1[i]]+1<a[x1[i]+1][y1[i]+1])
      {
      ok=1;
      // diagonala jos-dreapta
      a[x1[i]+1][y1[i]+1] = a[x1[i]][y1[i]]+1;
      j++;
      x2[j] = x1[i]+1;
      y2[j] = y1[i]+1;
      }

    if(x1[i]+1<=n && y1[i]-1>=0 && a[x1[i]+1][y1[i]-1]!=-1 && a[x1[i]][y1[i]]+1<a[x1[i]+1][y1[i]-1])
      {
      ok=1;
      // diagonala jos-stanga
      a[x1[i]+1][y1[i]-1] = a[x1[i]][y1[i]]+1;
      j++;
      x2[j] = x1[i]+1;
      y2[j] = y1[i]-1;
      }

    if(x1[i]-1>=1 && y1[i]-1>=0 && a[x1[i]-1][y1[i]-1]!=-1 && a[x1[i]][y1[i]]+1<a[x1[i]-1][y1[i]-1])
      {
      ok=1;
      // diagonala sus-stanga
      a[x1[i]-1][y1[i]-1] = a[x1[i]][y1[i]]+1;
      j++;
      x2[j] = x1[i]-1;
      y2[j] = y1[i]-1;
      }

    if(x1[i]-1>=1 && y1[i]+1<=m && a[x1[i]-1][y1[i]+1]!=-1 && a[x1[i]][y1[i]]+1<a[x1[i]-1][y1[i]+1])
      {
      ok=1;
      // diagonala sus-dreapta
      a[x1[i]-1][y1[i]+1] = a[x1[i]][y1[i]]+1;
      j++;
      x2[j] = x1[i]-1;
      y2[j] = y1[i]+1;
      }
    } // for
  for(i=1;i<=j;i++)
    {
    x1[i]=x2[i];
    y1[i]=y2[i];
    }
  } // while

j=1;
ok=1;
x1[1]=julieta[1];
y1[1]=julieta[2];

while(ok==1)
  {
  ok=0;
  x=j;
  j=0;
  for(i=1;i<=x;i++)
    {
    if(x1[i]+1<=n && b[x1[i]+1][y1[i]]!=-1 && b[x1[i]][y1[i]]+1<b[x1[i]+1][y1[i]])
      {
      ok=1;
      // merge in jos
      b[x1[i]+1][y1[i]] = b[x1[i]][y1[i]]+1;
      j++;
      x2[j] = x1[i]+1;
      y2[j] = y1[i];
      }

    if(x1[i]-1>=1 && b[x1[i]-1][y1[i]]!=-1 && b[x1[i]][y1[i]]+1<b[x1[i]-1][y1[i]])
      {
      ok=1;
      // merge in sus
      b[x1[i]-1][y1[i]] = b[x1[i]][y1[i]]+1;
      j++;
      x2[j] = x1[i]-1;
      y2[j] = y1[i];
      }

    if(y1[i]+1<=m && b[x1[i]][y1[i]+1]!=-1 && b[x1[i]][y1[i]]+1<b[x1[i]][y1[i]+1])
      {
      ok=1;
      // merge la dreapta
      b[x1[i]][y1[i]+1] = b[x1[i]][y1[i]]+1;
      j++;
      x2[j] = x1[i];
      y2[j] = y1[i]+1;
      }

    if(y1[i]-1>=0 && b[x1[i]][y1[i]-1]!=-1 && b[x1[i]][y1[i]]+1<b[x1[i]][y1[i]-1])
      {
      ok=1;
      // merge la stanga
      b[x1[i]][y1[i]-1] = b[x1[i]][y1[i]]+1;
      j++;
      x2[j] = x1[i];
      y2[j] = y1[i]-1;
      }

    if(x1[i]+1<=n && y1[i]+1<=m && b[x1[i]+1][y1[i]+1]!=-1 && b[x1[i]][y1[i]]+1<b[x1[i]+1][y1[i]+1])
      {
      ok=1;
      // diagonala jos-dreapta
      b[x1[i]+1][y1[i]+1] = b[x1[i]][y1[i]]+1;
      j++;
      x2[j] = x1[i]+1;
      y2[j] = y1[i]+1;
      }

    if(x1[i]+1<=n && y1[i]-1>=0 && b[x1[i]+1][y1[i]-1]!=-1 && b[x1[i]][y1[i]]+1<b[x1[i]+1][y1[i]-1])
      {
      ok=1;
      // diagonala jos-stanga
      b[x1[i]+1][y1[i]-1] = b[x1[i]][y1[i]]+1;
      j++;
      x2[j] = x1[i]+1;
      y2[j] = y1[i]-1;
      }

    if(x1[i]-1>=1 && y1[i]-1>=0 && b[x1[i]-1][y1[i]-1]!=-1 && b[x1[i]][y1[i]]+1<b[x1[i]-1][y1[i]-1])
      {
      ok=1;
      // diagonala sus-stanga
      b[x1[i]-1][y1[i]-1] = b[x1[i]][y1[i]]+1;
      j++;
      x2[j] = x1[i]-1;
      y2[j] = y1[i]-1;
      }

    if(x1[i]-1>=1 && y1[i]+1<=m && b[x1[i]-1][y1[i]+1]!=-1 && b[x1[i]][y1[i]]+1<b[x1[i]-1][y1[i]+1])
      {
      ok=1;
      // diagonala sus-dreapta
      b[x1[i]-1][y1[i]+1] = b[x1[i]][y1[i]]+1;
      j++;
      x2[j] = x1[i]-1;
      y2[j] = y1[i]+1;
      }
    } // for
  for(i=1;i<=j;i++)
    {
    x1[i]=x2[i];
    y1[i]=y2[i];
    }
  } // while

int min=10000;
for(i=1;i<=n;i++)
  for(j=1;j<=m;j++)
    if(a[i][j]>0 && a[i][j]==b[i][j] && min>a[i][j])
        {
        min=a[i][j];
        x=i;
	y=j;
	}

out.open("rj.out",ios::out);
out<<min+1<<" "<<x<<" "<<y;
out.close();
}