Cod sursa(job #1364416)

Utilizator razvanpaduraruPaduraru Razvan razvanpaduraru Data 27 februarie 2015 17:34:01
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.4 kb
#include <fstream>

using namespace std;
ifstream fin("rj.in");
ofstream fout("rj.out");
int A[101][101],X[100000],Y[100000],n,m,B[101][101];
const int di[]={-1,-1,-1,0,1,1,1,0};
const int dj[]={-1,0,1,1,1,0,-1,-1};
int inside(int i,int j)
{
    return i>=1 && i<=n && j>=1 && j<=m;
}
int main()
{
    int s=1,d=0,j,ir,jr,ij,jj;
    char a[255];
    fin>>n>>m;
    for(int i=0;i<=n;i++)
    {
        fin.getline(a,255);
        for(j=0;a[j]!=0;j++)
        {
          if(a[j]=='X')
          {
              A[i][j+1]=-1;
              B[i][j+1]=-1;
          }
          else if(a[j]==' ')
          {
              A[i][j+1]=0;
              B[i][j+1]=0;
          }
          else if(a[j]=='R')
          {
              d++;
              X[d]=i;
              Y[d]=j+1;
              ir=i;
              jr=j+1;
          }
          else
          {
              ij=i;
              jj=j+1;
          }
          }
    }
     for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
    {
        B[i][j]=A[i][j];
    }
    while(s<=d)
    {
        int i=X[s],j=Y[s];
    for(int c=0;c<=7;c++)
        {
            int inou=i+di[c],jnou=j+dj[c];
            if(inside(inou,jnou) && A[inou][jnou]==0)
            {
                A[inou][jnou]=A[i][j]+1;
                d++;
                X[d]=inou;
                Y[d]=jnou;
            }
        }
        s++;

    }
    A[ij][jj]=0;
    A[ir][jr]=0;
    s=1;d=1;
    X[100]={0};
    Y[100]={0};
    X[1]=ij;
    Y[1]=jj;
    while(s<=d)
    {
        int i=X[s],j=Y[s];
    for(int c=0;c<=7;c++)
        {
            int inou=i+di[c],jnou=j+dj[c];
            if(inside(inou,jnou) && B[inou][jnou]==0)
            {
                B[inou][jnou]=B[i][j]+1;
                d++;
                X[d]=inou;
                Y[d]=jnou;
            }
        }
        s++;

    }
    B[ij][jj]=0;
     B[ir][jr]=0;
    int dmin=99999,q,w;
     for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
          {
              if(A[i][j]==B[i][j] && A[i][j]!=0 && A[i][j]!=-1 && B[i][j]!=0 && B[i][j]!=-1)
              {
                  if(A[i][j]<dmin)
                  {
                      dmin=A[i][j];
                      q=i;
                      w=j;
                  }
              }
          }
    }
    fout<<dmin+1<<" "<<q<<" "<<w;




    return 0;
}