Cod sursa(job #2335362)

Utilizator AndreiGSGhiurtu Andrei AndreiGS Data 3 februarie 2019 22:50:03
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.44 kb
#include <fstream>
#include <queue>
#define N 105
using namespace std;

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

void citire(int Romeo[N][N], int Julieta[N][N], int &n, int &m, int &xJulieta, int &yJulieta, int &xRomeo, int &yRomeo)
{
  in>>n>>m;
  in.get();
  for(int i=0; i<n; i++)
  {
    char c[105];
    in.getline(c, 105);
    for(int j=0; j<m; j++)
    {
      if(c[j]=='X')
      {
        Romeo[i+1][j+1]=-1;
        Julieta[i+1][j+1]=-1;
      }
      if(c[j]=='J')
      {
        Julieta[i+1][j+1]=1;
        xJulieta=i+1;
        yJulieta=j+1;
      }
      if(c[j]=='R')
      {
        Romeo[i+1][j+1]=1;
        xRomeo=i+1;
        yRomeo=j+1;
      }
    }
  }
}

void bordare(int mat[N][N], int n, int m)
{
  for(int i=0; i<=n+1; i++)
  {
    mat[i][0]=-1;
    mat[i][m+1]=-1;
  }
  for(int i=0; i<=m+1; i++)
  {
    mat[0][i]=-1;
    mat[n+1][i]=-1;
  }
}

bool valid(int mat[N][N], int x, int y)
{
  if(mat[x][y]==0)
    return true;
  return false;
}

void Lee(int mat[N][N], int x, int y)
{
  int linie[8]= {-1, -1, 0, 1, 1, 1, 0, -1};
  int coloana[8]= {0, 1, 1, 1, 0, -1, -1, -1};
  queue<pair<int, int> > coada;
  coada.push(make_pair(x, y));

  while(!coada.empty())
  {
    pair<int, int> nod=coada.front();
    coada.pop();
    for(int poz=0; poz<8; poz++)
      if(valid(mat, nod.first+linie[poz], nod.second+coloana[poz]))
      {
        coada.push(make_pair(nod.first+linie[poz], nod.second+coloana[poz]));
        mat[nod.first+linie[poz]][nod.second+coloana[poz]]=mat[nod.first][nod.second]+1;
      }
  }
}

void loc(int Romeo[N][N], int Julieta[N][N], int n, int m, int xJulieta, int yJulieta, int xRomeo, int yRomeo, int &x, int &y, int &tmin)
{
    for(int i=1; i<=n; i++)
      for(int j=1; j<=m; j++)
        if(Romeo[i][j]>0 && Julieta[i][j]==Romeo[i][j] && tmin>Romeo[i][j])
        {
          x=i;
          y=j;
          tmin=Romeo[i][j];
        }
}

int main()
{
  int Romeo[N][N]={0}, Julieta[N][N]={0}, n, m, xintalnire, yintalnire, tmin=100000;
  int xRomeo, yRomeo;
  int xJulieta, yJulieta;
  citire(Romeo, Julieta, n, m, xJulieta, yJulieta, xRomeo, yRomeo);
  bordare(Romeo, n, m);
  bordare(Julieta, n, m);
  Lee(Romeo, xRomeo, yRomeo);
  Lee(Julieta, xJulieta, yJulieta);
  loc(Romeo, Julieta, n, m, xJulieta, yJulieta, xRomeo, yRomeo, xintalnire, yintalnire, tmin);
  out<<tmin<<' '<<xintalnire<<' '<<yintalnire;
  return 0;
}