Cod sursa(job #2978449)

Utilizator davidenko22Stancu David-Andrei davidenko22 Data 13 februarie 2023 19:26:26
Problema Rj Scor 50
Compilator c-64 Status done
Runda Arhiva de probleme Marime 3.29 kb
#include <stdio.h>
#include <stdlib.h>

#define VAL_MAX 10000 /// N * M
#define NM_MAX 100
int n, m; /// le folosesc in functie, de asta le-am declarat global
char a[NM_MAX][NM_MAX]; /// a[][] este matricea primita la intrare
int ro[NM_MAX + 2][NM_MAX + 2],ju[NM_MAX + 2][NM_MAX + 2]; /// ro[][] este matricea in care voi efectua Lee-ul pentru Romeo, iar ju[][] este matricea in care voi efectua Lee-ul pentru Julietas
short int sir[2][VAL_MAX]; /// am facut un calcul si aceasta matrice intra pe short int si am vrut sa economisesc memorie
int dl[8] = { -1, 1, 0, 0, -1, -1, 1, 1 }; /// vectorii pentru cele 8 directii, orizontala, verticala si diagonale
int dc[8] = { 0, 0, -1, 1, -1, 1, -1, 1 };

void Lee( int r, int q, char ch ) { /// am facut Lee-ul ca functie pt ca eu vreau sa il fac si pentru Romeo si pentru Julieta si nu doream sa repet cod
    int l, c, st, dr, xl, yc, i;
    for ( l = 1; l <= n; l++ ) {
      for ( c = 1; c <= m; c++ ) {
        if ( ch == 'R' ) { /// verific daca ch curent este Romeo
          if ( a[l][c] == 'X' )
            ro[l][c] = -1;
        }
        else {
          if ( a[l][c] == 'X' )
            ju[l][c] = -2;
        }
      }
    }
    if ( ch == 'R' )
      ro[r][q] = 1;
    else
      ju[r][q] = 1;
    st = dr = 0;
    sir[0][dr] = r;
    sir[1][dr] = q;
    while (st <= dr) {
      for ( i = 0; i <= 7; i++ ) { /// parcurg cele 8 directii, adica aplic Lee
        xl = sir[0][st] + dl[i];
        yc = sir[1][st] + dc[i];
        if ( ch == 'R') {
					if ( 0 < xl && xl <= n && 0 < yc && yc <= m && ro[xl][yc] == 0 ) {
					  ro[xl][yc] = ro[sir[0][st]][sir[1][st]] + 1;
					  dr++;
					  sir[0][dr] = xl;
					  sir[1][dr] = yc;
					}
        }
        else if ( 0 < xl && xl <= n && 0 < yc && yc <= m && ju[xl][yc] == 0 ) {
				  ju[xl][yc] = ju[sir[0][st]][sir[1][st]] + 1;
				  dr++;
				  sir[0][dr] = xl;
				  sir[1][dr] = yc;
        }
      }
      st++;
    }
}

int main()
{
    FILE *fin, *fout;
    fin = fopen( "rj.in", "r" );
    fout = fopen( "rj.out", "w" );
    int l, c, st, q, min;
    fscanf( fin, "%d%d", &n, &m );
    fgetc(fin);
    for ( l = 1; l <= n; l++ ) {
      for ( c = 1; c <= m; c++ ) {
        a[l][c] = fgetc(fin);
      }
      fgetc(fin);
    }
    for ( l = 0; l <= n + 1; l++ )
      ro[l][0] = ro[l][m + 1] = ju[l][0] = ju[l][m + 1] = -3; /// bordare
    for ( c = 0; c <= m + 1; c++ )
      ro[0][c] = ro[n + 1][c] = ju[0][c] = ju[n + 1][c] = -3; /// bordare
    for ( l = 1; l <= n; l++ ) { /// stiu ca aici puteam sa ma opresc cand gaseam R si J, adica sa fac cautarea normala, dar am ales sa parcurg toata matricea pentru ca mi se pare mai clar asa
      for ( c = 1; c <= m; c++ ) {
        if ( a[l][c] == 'R' )
          Lee( l, c, 'R' );
        else if ( a[l][c] == 'J')
          Lee( l, c, 'J' );
      }
    }
    st = q = 1;
    min = VAL_MAX;
    for ( l = 1; l <= n; l++ ) {
      for ( c = 1; c <= m; c++ ) {
        if ( ro[l][c] == ju[l][c] && ro[l][c] != -1 && ro[l][c] < min) {
			   min = ro[l][c];
			   st = l;
			   q = c;
        }
      }
    }
    fprintf( fout,"%d %d %d", min, st, q);
    return 0;
    fclose(fin);
    fclose(fout);
    /// imi pare rau ca programul este destul de incalcit, dar am incercat sa il fac cat mai clar
}