Cod sursa(job #2018981)

Utilizator IancuVladIancu Vlad IancuVlad Data 6 septembrie 2017 15:32:57
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.66 kb
#include<iostream>
#include<fstream>
#include<queue>
#include<iomanip>
using namespace std;

fstream fin("rj.in",ios::in);
fstream fout("rj.out",ios::out);

const int NMax=105;

int Min=NMax*10;

int matR[NMax][NMax], matJ[NMax][NMax],N,M;

int xRomeo,yRomeo,xJulieta,yJulieta;

int xOptim,yOptim;

int di[8]={-1,-1,0,1,1,1,0,-1};
int dj[8]={0,1,1,1,0,-1,-1,-1};

void Input()
{fin>>N>>M;
 
 int i,j;
 fin.get();
 for(i=1;i<=N;i++)
 {  char a[NMax];
    fin.getline(a,NMax);
   for(j=1;j<=M;j++)
   {
     if(a[j-1]=='R') {xRomeo=i; yRomeo=j; matR[i][j]=0;}
     if(a[j-1]=='J') {xJulieta=i; yJulieta=j; matJ[i][j]=0;}

     if(a[j-1]==' ') {matR[i][j]=0; matJ[i][j]=0;}
     if(a[j-1]=='X') {matR[i][j]=-1; matJ[i][j]=-1;}//pui minus unu cand trimiti sursa

   }
 cout<<endl;}
}

bool OKR(int x,int y)
{
 if(x<1 || x>N) return false;
 if(y<1 || y>M) return false;

 if(x==xRomeo && y==yRomeo)return false;
  
 if(matR[x][y]!=0) return false; 

 return true;
} 
bool OKJ(int x,int y)
{
 if(x<1 || x>N) return false;
 if(y<1 || y>M) return false;

if(x==xJulieta && y==yJulieta) return false; 

 if(matJ[x][y]!=0) return false; 

 return true;
} 

void LeeR(int xStart, int yStart)
{ queue <pair<int,int> > coada;
  coada.push(make_pair(xStart,yStart));
  
  while(!coada.empty())
  {
   int x=coada.front().first,y=coada.front().second;

   for(int i=0;i<8;i++)
   {if(OKR(x+di[i],y+dj[i])) 
    {matR[x+di[i]][y+dj[i]]=matR[x][y]+1;
     coada.push(make_pair(x+di[i],y+dj[i]));
    }
 
   } 
   coada.pop();
  }



}
void LeeJ(int xStart, int yStart)
{ queue <pair<int,int> > coada;
  coada.push(make_pair(xStart,yStart));
  
  while(!coada.empty())
  {
   int x=coada.front().first,y=coada.front().second;

   for(int i=0;i<8;i++)
   {if(OKJ(x+di[i],y+dj[i])) 
    {matJ[x+di[i]][y+dj[i]]=matJ[x][y]+1;
     coada.push(make_pair(x+di[i],y+dj[i]));
    }
 
   } 
   coada.pop();
  }



}

void CautaOptim()
{if(xRomeo==xJulieta && yRomeo==yJulieta) {xOptim=xRomeo; yOptim=yRomeo; Min=0; return; }
 xOptim=NMax; yOptim=NMax;
 int dist=NMax*10;
 for(int i=1;i<=N;i++)
  for(int j=1;j<+M;j++)
 if(matR[i][j]>0&&matJ[i][j]>0) 
 if(matR[i][j]==matJ[i][j])
   {
    if(matR[i][j]<dist) {xOptim=i; yOptim=j; dist=matR[i][j]; }
     else if(matR[i][j]==dist)
           if(i<xOptim) {dist=matR[i][j]; xOptim=i; yOptim=j;  }
            else if(i==xOptim)
                  if(j<yOptim) {dist=matR[i][j]; xOptim=i; yOptim=j; }
  
   }

Min=dist;
}

int main()
{Input();
LeeR(xRomeo,yRomeo);
LeeJ(xJulieta,yJulieta);
CautaOptim();

fout<<Min+1<<' '<<xOptim<<' '<<yOptim;

return 0;

}