Cod sursa(job #2416600)

Utilizator cata_albuCatalin Albu cata_albu Data 27 aprilie 2019 19:39:46
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.63 kb
#include <fstream>
#include <iostream>
#include <queue>
#define MAX 105

using namespace std;

ifstream r("rj.in");
ofstream w("rj.out");

int n,m,rsl,rsc,jsl,jsc,mi=MAX,li,co;
int dl[]={-1,-1,0,1,1,1,0,-1},dc[]={0,1,1,1,0,-1,-1,-1};
int ju[MAX][MAX],ro[MAX][MAX];


///functie pentru citirea datelor de intrare
void citire(){
  char c;
  r>>n>>m;
  int i=1,j=1;
  r.get();
  while(!r.eof()){
    r.get(c);
    if(c=='X') ju[i][j]=ro[i][j]=-1;
    if(c=='R') {rsl=i;rsc=j;}
    if(c=='J') {jsl=i; jsc=j;}
    if(c=='\n') { i++; j=1; }
    else j++;
  }
}

///functie pentru afisare
void afis()
{for(int i=1;i<=n;i++){for(int j=1;j<=m;j++) w<<ro[i][j]<<" "; w<<'\n';}}

///functie pentru bordare
void bordare(){
  for(int i=0;i<=n+1;i++)
    ju[i][0]=ju[i][m+1]=ro[i][0]=ro[i][n+1]=-1;
  for(int i=0;i<=m+1;i++)
      ju[0][i]=ju[n+1][i]=ro[0][i]=ro[n+1][i]=-1;

}

///algoritmul lui Lee
 void lee(int a[][MAX], int ls, int cs){
   queue < pair <int, int> > Q;
   Q.push({ls,cs});
   a[ls][cs]=1;
   while(!Q.empty())
   {
     int l=Q.front().first;
     int c=Q.front().second;
     Q.pop();
     for(int i=0;i<8;i++)
     {
       int ln=l+dl[i];
       int cn=c+dc[i];
       if(a[ln][cn]==0){
         Q.push({ln, cn});
       a[ln][cn]=a[l][c]+1;
     }
     }
   }

 }

void exe(){
  lee(ro,rsl,rsc);
  lee(ju,jsl,jsc);
  for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    if(ro[i][j]==ju[i][j]&&ro[i][j]>0&&ro[i][j]<mi)
      {
        mi=ro[i][j];
        li=i;
        co=j;
      }
}

int main(){
  citire();
  bordare();
  exe();
  w<<li<<" "<<co<<" "<<mi;
  return 0;
}