Cod sursa(job #2290548)

Utilizator alex.cojocaruAlex Cojocaru alex.cojocaru Data 26 noiembrie 2018 17:42:51
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.03 kb
#include <iostream>
#include <stdio.h>
#include <queue>

#define NMAX 100
#define DIRMAX 4
#define INFINIT 100*100+1

using namespace std;

struct elem {
  int l ;
  int c ;
};

char mat [ NMAX + 1 ] [ NMAX + 1 ] ;
int dr [ NMAX + 1 ] [ NMAX + 1 ] ;
int dj [ NMAX + 1 ] [ NMAX + 1 ] ;
int dirl [ DIRMAX ] {-1, 0, +1, 0} ; /// nord, vest, sud, est
int dirc [ DIRMAX ] {0, -1, 0, +1} ;
queue <elem> q ;

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

void bfs (int n, int m, int x, int y, int d[NMAX+1][NMAX+1]) {
  int i ;
  elem first ;
  bordare(n, m, d) ;
  q.push({x, y}) ;
  d[x][y] = 0 ;
  while (!q.empty()) {
    first.l = q.front().l ;
    first.c = q.front().c ;
    for (i = 0 ; i < DIRMAX ; i++ ) {
      if (mat[first.l+dirl[i]][first.c+dirc[i]] != 'X' && d[first.l+dirl[i]][first.c+dirc[i]] == 0 ) {
        d[first.l+dirl[i]][first.c+dirc[i]] = d[first.l][first.c] + 1 ;
        q.push({first.l+dirl[i], first.c+dirc[i]}) ;
      }
    }
    q.pop() ;
  }
}

int main() {

  FILE *fin, *fout ;
  fin = fopen ("rj.in", "r" ) ;
  fout = fopen ("rj.out", "w" ) ;
  int n, i, m, roml, romc, jull, julc, p1, p2, minim, j ; /// pozitia romului
  fscanf (fin, "%d%d\n", &n, &m ) ;
  for (i = 1 ; i <= n ; i++ ) {
    for (j = 1 ; j <= m ; j++ ) {
      fscanf (fin, "%c", &mat[i][j] ) ;
      if (mat[i][j] == 'R' ) {
        roml = i ;
        romc = j ;
      }else if (mat[i][j] == 'J' ) {
        jull = i ;
        julc = j ;
      }
    }
    fgetc(fin) ;
  }
  bfs(n, m, roml, romc, dr) ;
  bfs(n, m, jull, julc, dj) ;
  minim = INFINIT ;
  for (i = 1 ; i <= n ; i++ ) {
    for (j = 1 ; j <= m ; j++ ) {
      if ( (dr[i][j] == dj[i][j] && minim > dr[i][j] ) && dr[i][j] != 0 ) {
        minim = dr[i][j] ;
        p1 = i ;
        p2 = j ;
      }
    }
  }
  fprintf (fout, "%d %d %d\n", minim, p1, p2 ) ;
  return 0;
}