Cod sursa(job #3005367)

Utilizator teochess2017Togan Teodor-Bogdan teochess2017 Data 16 martie 2023 22:02:41
Problema Rj Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 6.87 kb
#include <iostream>
#include <stdio.h>

using namespace std;

#define MAXNM 100
#define NRDIR 8
#define MOD 800
#define NRDIR2 4

struct rj{
  int rom, jul;
};
struct coord{
  rj l, c;
};

int mat[MAXNM + 2][MAXNM + 2];///!!!!!!!!!!!!char
rj dist[MAXNM + 2][MAXNM + 2];
coord q[MOD];
int dirl[NRDIR] = {0, 1, 0, -1, -1, 1, -1, 1}, dirc[NRDIR] = {1, 0, -1, 0, 1, 1, -1, -1};

FILE *fin, *fout;

int BFS(){
  rj p, u, cu;
  int i, lenght = 2, lin = -1, col;
  bool intalnit = false;
  u.rom = u.jul = 1;
  p.rom = p.jul = 0;
  dist[q[0].l.rom][q[0].c.rom].rom = 1;
  dist[q[0].l.jul][q[0].c.jul].jul = 1;
  while(((p.rom < u.rom) || (p.jul < u.jul)) && (!intalnit)){
    cu = {u.rom, u.jul};
    while((p.rom < cu.rom) || (p.jul < cu.jul)){
      for(i = 0; i < NRDIR; i++){

        if((p.rom < cu.rom) && (mat[q[p.rom % MOD].l.rom + dirl[i]][q[p.rom % MOD].c.rom + dirc[i]] == 1) && (dist[q[p.rom % MOD].l.rom + dirl[i]][q[p.rom % MOD].c.rom + dirc[i]].rom == 0)){
          dist[q[p.rom % MOD].l.rom + dirl[i]][q[p.rom % MOD].c.rom + dirc[i]].rom = lenght;
          if(dist[q[p.rom % MOD].l.rom + dirl[i]][q[p.rom % MOD].c.rom + dirc[i]].jul == lenght){
            if(intalnit == true){
              if((q[p.rom % MOD].l.rom + dirl[i]) < lin){
                lin = q[p.rom % MOD].l.rom + dirl[i];
                col = q[p.rom % MOD].c.rom + dirc[i];
              }else if((q[p.rom % MOD].l.rom + dirl[i]) < lin == lin){
                if((q[p.rom % MOD].c.rom + dirc[i]) < col){
                  col = q[p.rom % MOD].c.rom + dirc[i];
                }
              }
            }else{
              intalnit = true;
              lin = q[p.rom % MOD].l.rom + dirl[i];
              col = q[p.rom % MOD].c.rom + dirc[i];
            }
          }
          q[u.rom % MOD].l.rom = q[p.rom % MOD].l.rom + dirl[i];
          q[u.rom % MOD].c.rom = q[p.rom % MOD].c.rom + dirc[i];
          u.rom++;
        }



        if((p.jul < cu.jul) && (mat[q[p.jul % MOD].l.jul + dirl[i]][q[p.jul % MOD].c.jul + dirc[i]] == 1) && (dist[q[p.jul % MOD].l.jul + dirl[i]][q[p.jul % MOD].c.jul + dirc[i]].jul == 0)){
          dist[q[p.jul % MOD].l.jul + dirl[i]][q[p.jul % MOD].c.jul + dirc[i]].jul = lenght;
          if(dist[q[p.jul % MOD].l.jul + dirl[i]][q[p.jul % MOD].c.jul + dirc[i]].rom == lenght){
            if(intalnit == true){
              if((q[p.jul % MOD].l.jul + dirl[i]) < lin){
                lin = q[p.jul % MOD].l.jul + dirl[i];
                col = q[p.jul % MOD].c.jul + dirc[i];
              }else if((q[p.jul % MOD].l.jul + dirl[i]) < lin == lin){
                if((q[p.jul % MOD].c.jul + dirc[i]) < col){
                  col = q[p.jul % MOD].c.jul + dirc[i];
                }
              }
            }else{
              intalnit = true;
              lin = q[p.jul % MOD].l.jul + dirl[i];
              col = q[p.jul % MOD].c.jul + dirc[i];
            }
          }
          q[u.jul % MOD].l.jul = q[p.jul % MOD].l.jul + dirl[i];
          q[u.jul % MOD].c.jul = q[p.jul % MOD].c.jul + dirc[i];
          u.jul++;
        }

      }
      if(p.rom < cu.rom){
        p.rom++;
      }
      if(p.jul < cu.jul){
        p.jul++;
      }
    }
    lenght++;
  }
  if(lin != -1){
    fprintf(fout, "%d %d %d", lenght - 1, lin, col);
  }
  return lin;
}
void BFS2(){
  rj p, u, cu;
  int i, lenght = 2, lin = -1, col;
  bool intalnit = false;
  u.rom = u.jul = 1;
  p.rom = p.jul = 0;
  dist[q[0].l.rom][q[0].c.rom].rom = 1;
  dist[q[0].l.jul][q[0].c.jul].jul = 1;
  while(((p.rom < u.rom) || (p.jul < u.jul)) && (!intalnit)){
    cu = {u.rom, u.jul};
    while((p.rom < cu.rom) || (p.jul < cu.jul)){
      for(i = 0; i < NRDIR2; i++){

        if((p.rom < cu.rom) && (mat[q[p.rom % MOD].l.rom + dirl[i]][q[p.rom % MOD].c.rom + dirc[i]] == 1) && (dist[q[p.rom % MOD].l.rom + dirl[i]][q[p.rom % MOD].c.rom + dirc[i]].rom == 0)){
          dist[q[p.rom % MOD].l.rom + dirl[i]][q[p.rom % MOD].c.rom + dirc[i]].rom = lenght;
          if(dist[q[p.rom % MOD].l.rom + dirl[i]][q[p.rom % MOD].c.rom + dirc[i]].jul == lenght){
            if(intalnit == true){
              if((q[p.rom % MOD].l.rom + dirl[i]) < lin){
                lin = q[p.rom % MOD].l.rom + dirl[i];
                col = q[p.rom % MOD].c.rom + dirc[i];
              }else if((q[p.rom % MOD].l.rom + dirl[i]) < lin == lin){
                if((q[p.rom % MOD].c.rom + dirc[i]) < col){
                  col = q[p.rom % MOD].c.rom + dirc[i];
                }
              }
            }else{
              intalnit = true;
              lin = q[p.rom % MOD].l.rom + dirl[i];
              col = q[p.rom % MOD].c.rom + dirc[i];
            }
          }
          q[u.rom % MOD].l.rom = q[p.rom % MOD].l.rom + dirl[i];
          q[u.rom % MOD].c.rom = q[p.rom % MOD].c.rom + dirc[i];
          u.rom++;
        }



        if((p.jul < cu.jul) && (mat[q[p.jul % MOD].l.jul + dirl[i]][q[p.jul % MOD].c.jul + dirc[i]] == 1) && (dist[q[p.jul % MOD].l.jul + dirl[i]][q[p.jul % MOD].c.jul + dirc[i]].jul == 0)){
          dist[q[p.jul % MOD].l.jul + dirl[i]][q[p.jul % MOD].c.jul + dirc[i]].jul = lenght;
          if(dist[q[p.jul % MOD].l.jul + dirl[i]][q[p.jul % MOD].c.jul + dirc[i]].rom == lenght){
            if(intalnit == true){
              if((q[p.jul % MOD].l.jul + dirl[i]) < lin){
                lin = q[p.jul % MOD].l.jul + dirl[i];
                col = q[p.jul % MOD].c.jul + dirc[i];
              }else if((q[p.jul % MOD].l.jul + dirl[i]) < lin == lin){
                if((q[p.jul % MOD].c.jul + dirc[i]) < col){
                  col = q[p.jul % MOD].c.jul + dirc[i];
                }
              }
            }else{
              intalnit = true;
              lin = q[p.jul % MOD].l.jul + dirl[i];
              col = q[p.jul % MOD].c.jul + dirc[i];
            }
          }
          q[u.jul % MOD].l.jul = q[p.jul % MOD].l.jul + dirl[i];
          q[u.jul % MOD].c.jul = q[p.jul % MOD].c.jul + dirc[i];
          u.jul++;
        }

      }
      if(p.rom < cu.rom){
        p.rom++;
      }
      if(p.jul < cu.jul){
        p.jul++;
      }
    }
    lenght++;
  }
  if(lin != -1){
    fprintf(fout, "%d %d %d", lenght - 1, lin, col);
  }
}

int main()
{
    char ch;
    int n, m, l, c, retval;
    fin = fopen("rj.in", "r");
    fscanf(fin, "%d%d", &n, &m);
    for(l = 1; l <= n; l++){
      ch = fgetc(fin);
      for(c = 1; c <= m; c++){
        ch = fgetc(fin);
        if(ch == 'R'){
          mat[l][c] = 'R';
          q[0].l.rom = l;
          q[0].c.rom = c;
        }else if(ch == 'J'){
          mat[l][c] = 'J';
          q[0].l.jul = l;
          q[0].c.jul = c;
        }else if(ch == ' '){
          mat[l][c] = 1;
        }
      }
    }
    fclose(fin);
    fout = fopen("rj.out", "w");
    retval = BFS();
    if(retval != -1){
      BFS2();
    }
    fclose(fout);
    return 0;
}