Cod sursa(job #2079359)

Utilizator borscalinCalin-Stefan Georgescu borscalin Data 1 decembrie 2017 10:38:55
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.07 kb
#include <cstdio>
#include <algorithm>
#include <queue>
#define INF 300

using namespace std;

struct coordonate{
  char x,y;
};

queue <coordonate> q;

char a[102][102];
int distr[102][102];
int distj[102][102];
char dirl[]={-1,-1,0,1,1,1,0,-1};
char dirc[]={0,1,1,1,0,-1,-1,-1};

int main(){
    freopen("rj.in","r",stdin);
    freopen("rj.out","w",stdout);
    int n,m,l,c,min,i;
    coordonate tmp,first,romeo,julieta,poz;
    scanf("%d%d\n",&m,&n);
    min=n;
    n=m;
    m=min;
    for (l=0;l<=n+1;l++)
      for (c=0;c<=m+1;c++)
        a[l][c]=distr[l][c]=distj[l][c]=INF;
    for (l=1;l<=n;l++){
      for (c=1;c<=m;c++){
        a[l][c]=fgetc(stdin);
        if (a[l][c]=='R')
          romeo.x=l,romeo.y=c;
        else if (a[l][c]=='J')
          julieta.x=l,julieta.y=c;
      }
      fgetc(stdin);
    }
    distr[romeo.x][romeo.y]=1;
    tmp.x=romeo.x;
    tmp.y=romeo.y;
    q.push(tmp);
    while (!q.empty()){
      first=q.front();
      q.pop();
      for (i=0;i<8;i++){
        tmp.x=first.x+dirl[i];
        tmp.y=first.y+dirc[i];
        if (a[tmp.x][tmp.y]==' '){
            if (distr[first.x][first.y]+1<distr[tmp.x][tmp.y]){
              distr[tmp.x][tmp.y]=distr[first.x][first.y]+1;
              q.push(tmp);
            }
        }
      }
    }
    distj[julieta.x][julieta.y]=1;
    tmp.x=julieta.x;
    tmp.y=julieta.y;
    q.push(tmp);
    while (!q.empty()){
      first=q.front();
      q.pop();
      for (i=0;i<8;i++){
        tmp.x=first.x+dirl[i];
        tmp.y=first.y+dirc[i];
        if (a[tmp.x][tmp.y]==' '){
            if (distj[first.x][first.y]+1<distj[tmp.x][tmp.y]){
              distj[tmp.x][tmp.y]=distj[first.x][first.y]+1;
              q.push(tmp);
            }
        }
      }
    }
    min=INF;
    for (l=1;l<=n;l++)
      for (c=1;c<=m;c++)
        if (a[l][c]==' ')
          if (distr[l][c]==distj[l][c])
            if (distr[l][c]<min && distr[l][c]!=INF)
              min=distr[l][c],poz.x=l,poz.y=c;
    printf("%d %d %d",min,poz.x,poz.y);
    return 0;
}