Cod sursa(job #2303543)

Utilizator isa_tudor_andreiAndrei Tudor isa_tudor_andrei Data 16 decembrie 2018 15:23:33
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.79 kb
#include <bits/stdc++.h>
#define NMAX 105
using namespace std;

pair<int,int> q[NMAX*NMAX],r,t,x,y;
int romeo[NMAX][NMAX];
int julieta[NMAX][NMAX];

int dirLin[] = {0,1,0,-1};
int dirCol[] = {1,0,-1,0};

int main() {
    freopen("rj.in","r",stdin);
    freopen("rj.out","w",stdout);
    int n,m,i,j,st,dr;
    char ch;
    scanf("%d%d\n",&n,&m);
    for( i = 1; i <= n; i ++ ) {
      for( j = 1; j <= m; j ++ ) {
        ch = getc(stdin);
        printf("%c",ch);
        if( ch == 'J' )
          t.first = i, t.second = j;
        if( ch == 'R' )
          r.first = i, r.second = j;
        if( ch == 'X' )
          romeo[i][j] = julieta[i][j] = -2;
        if( ch == ' ' )
          romeo[i][j] = julieta[i][j] = -1;
      }
    }
    st = 0;
    dr = -1;
    q[++dr] = r;
    while( st <= dr ) {
      x = q[st++];
      for( i = 0; i < 4; i ++ ) {
        y.first = x.first + dirLin[i];
        y.second = x.second + dirCol[i];
        if( romeo[y.first][y.second] == -1 || y == t ) {
           q[++dr] = y;
           romeo[y.first][y.second] = 1 + romeo[x.first][x.second];
        }
      }
    }
    st = 0;
    dr = -1;
    q[++dr] = t;
    while( st <= dr ) {
      x = q[st++];
      for( i = 0; i < 4; i ++ ) {
        y.first = x.first + dirLin[i];
        y.second = x.second + dirCol[i];
        if( julieta[y.first][y.second] == -1 || y == r ) {
           q[++dr] = y;
           julieta[y.first][y.second] = 1 + julieta[x.first][x.second];
        }
      }
    }
    int ans = NMAX*NMAX;
    int ymin,xmin;
    for( i = 1; i <= n; i ++ )
      for( j = 1; j <= m; j ++ )
        if( romeo[i][j] == julieta[i][j] && romeo[i][j] > 0 )
          ans = min(ans,romeo[i][j]),xmin = i,ymin = j;
    printf("%d %d %d",ans,xmin,ymin);
    return 0;
}