Cod sursa(job #2147090)

Utilizator ivan.tudorIvan Tudor ivan.tudor Data 28 februarie 2018 14:06:01
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.89 kb
#include <iostream>
#include<cstdio>
using namespace std;
struct poz{
  int l,c,dist;
};
int dl[]={-1,-1,0,1,1,1,0,-1};
int dc[]={0,1,1,1,0,-1,-1,-1};
const int N=105;
poz q[N*N];
int mat[N][N];
int distj[N][N],distr[N][N];
poz rom,jul;
int main()
{
    FILE*fin,*fout;
    fin=fopen("rj.in","r");
    fout=fopen("rj.out","w");
    int n,m,i,j,dr=-1,st=0;
    poz x,y;
    char c;
    fscanf(fin,"%d%d",&n,&m);
    fgetc(fin);
    for(i=1;i<=n;i++){
      for(j=1;j<=m && c!='\n';j++){
        c=fgetc(fin);
        if(c==' ');
          mat[i][j]=0;
        if(c=='X')
          mat[i][j]=1;
        if(c=='R'){
          rom.l=i;
          rom.c=j;
          rom.dist=1;
        }
        if(c=='J'){
          jul.l=i;
          jul.c=j;
          jul.dist=1;
        }
      }
      if(c!='\n')
        fgetc(fin);
      c=0;
    }
    q[++dr]=rom;
    distr[rom.l][rom.c]=1;
    while(st<=dr){
      x=q[st++];
      for(i=0;i<8;i++){
        y.l=x.l+dl[i];
        y.c=x.c+dc[i];
        y.dist=x.dist+1;
        if(y.l>=1 && y.l<=n && y.c>=1 && y.c<=m && mat[y.l][y.c]==0 && distr[y.l][y.c]==0){
          q[++dr]=y;
          distr[y.l][y.c]=y.dist;
        }
      }
    }
    st=0;
    dr=-1;
    q[++dr]=jul;
    distj[jul.l][jul.c]=1;
    while(st<=dr){
      x=q[st++];
      for(i=0;i<8;i++){
        y.l=x.l+dl[i];
        y.c=x.c+dc[i];
        y.dist=x.dist+1;
        if(y.l>=1 && y.l<=n && y.c>=1 && y.c<=m && mat[y.l][y.c]==0 && distj[y.l][y.c]==0){
          q[++dr]=y;
          distj[y.l][y.c]=y.dist;
        }
      }
    }
    int imin,jmin,tmin=N*N+1;
    for(i=1;i<=n;i++)
      for(j=1;j<=m;j++){
        if(distj[i][j]!=0 && distj[i][j]==distr[i][j] && distj[i][j]<tmin){
          tmin=distj[i][j];
          imin=i;
          jmin=j;
        }
      }
    fprintf(fout,"%d %d %d",tmin,imin,jmin);
    return 0;
}