Cod sursa(job #3261384)

Utilizator Grama2008Grama Andrei Teodor Grama2008 Data 5 decembrie 2024 18:10:52
Problema Rj Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.89 kb
#include <iostream>

using namespace std;

struct p{
  int x;
  int y;
  int time;
};

int n,m,fi,fj,tmin,first,last;

int iR,jR,iJ,jJ;

int    row[8]={-1,-1,-1, 0, 1, 1,  1, 0};

int column[8]={-1, 0, 1, 1, 1, 0, -1, -1};

int R[105][105],J[105][105];

bool Rver[105][105], Jver[105][105];

p v[20005];

int valid_move_R(int i, int j){
    if (i<1 || i>n || j<1 || j>m){
      return 0;
    }
    if (Rver[i][j]==1){
      return 0;
    }
    if (R[i][j]==2000000){
      return 0;
    }
    Rver[i][j]=1;
    return 1;
}

int valid_move_J(int i, int j){
    if (i<1 || i>n || j<1 || j>m){
      return 0;
    }
    if (Jver[i][j]==1){
      return 0;
    }
    if (J[i][j]==2000000){
      return 0;
    }
    Jver[i][j]=1;
    return 1;
}

void lee_R(){
    int first=0,last=1;
    v[first].x=iR;
    v[first].y=jR;
    v[first].time=1;
    R[v[first].x][v[first].y]=v[first].time;
    while (first<last){
        Rver[v[first].x][v[first].y]=1;
        for (int i=0;i<8;i++){
            if (valid_move_R(v[first].x+row[i],v[first].y+column[i])){
                v[last].x=v[first].x+row[i];
                v[last].y=v[first].y+column[i];
                v[last].time=v[first].time+1;
                R[v[last].x][v[last].y]=v[last].time;
                last++;
            }
        }
        first++;
    }
    /*for (int i=1;i<=n;i++){
      for (int j=1;j<=m;j++){
        if(R[i][j]==2000000){
          printf("  X");
        }
        else{
            if (int(R[i][j])<10){
                printf("  %d", int(R[i][j]));
            }
            else if (int(R[i][j])<100){
                printf(" %d", int(R[i][j]));
            }
            else
            printf("%d", int(R[i][j]));
        }
      }
      printf("\n");
    }
    printf("\n\n");*/
}



void lee_J(){
    int first=0,last=1;
    v[first].x=iJ;
    v[first].y=jJ;
    v[first].time=1;
    J[v[first].x][v[first].y]=v[first].time;
    while (first<last){
        Jver[v[first].x][v[first].y]=1;
        for (int i=0;i<8;i++){
            if (valid_move_J(v[first].x+row[i],v[first].y+column[i])){
                v[last].x=v[first].x+row[i];
                v[last].y=v[first].y+column[i];
                v[last].time=v[first].time+1;
                J[v[last].x][v[last].y]=v[last].time;
                last++;
            }
        }
        first++;
    }
    /*for (int i=1;i<=n;i++){
      for (int j=1;j<=m;j++){
        if(J[i][j]==2000000){
            printf("  X");
        }
        else{
            if (int(J[i][j])<10){
                printf("  %d", int(J[i][j]));
            }
            else if (int(J[i][j])<100){
                printf(" %d", int(J[i][j]));
            }
            else
            printf("%d", int(J[i][j]));
        }
      }
      printf("\n");
    }
    */
}

FILE *fin, *fout;

int main()
{
    fin=fopen("rj.in", "r");
    fscanf(fin, "%d%d", &n,&m);
    fgetc(fin);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            fscanf(fin, "%c", &R[i][j]);
            if (R[i][j]=='X'){
                R[i][j]=2000000;
            }
            if (R[i][j]==' '){
                R[i][j]=2000002;
            }
            J[i][j]=R[i][j];
            if (R[i][j]=='R'){
                iR=i;
                jR=j;
                R[i][j]=2000001;
            }
            if (J[i][j]=='J'){
                iJ=i;
                jJ=j;
                J[i][j]=2000002;
            }
        }
        fgetc(fin);
    }
    fclose(fin);
    lee_R();
    lee_J();
    tmin=10005;
    for (int i=1;i<=n;i++)
      for (int j=1;j<=m;j++)
        if (R[i][j]==J[i][j] && R[i][j]<tmin){
          fi=i;
          fj=j;
          tmin=R[i][j];
        }
    fout=fopen("rj.out", "w");
    fprintf(fout, "%d %d %d", tmin, fi, fj);
    fclose(fout);
    return 0;
}