Cod sursa(job #2138462)

Utilizator MelacasKorian Ebraahim Melacas Data 21 februarie 2018 17:43:04
Problema Rj Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 2.81 kb
#include <stdio.h>
#include <stdlib.h>

int main()
{
    FILE* in = fopen("rj.in","r");
    FILE* out = fopen("rj.out","w");

    int n = 0, m = 0, i = 0, j = 0;
    fscanf(in,"%d %d\n",&n,&m);

    int **romeo = (int**) malloc((n + 2) * sizeof(int*));
    for (i = 0 ; i < n + 2 ; i++)
        romeo[i] = (int*) calloc(m + 2, sizeof(int));

    int **julieta = (int**) malloc((n + 2) * sizeof(int*));
    for (i = 0 ; i < n + 2 ; i++)
        julieta[i] = (int*) calloc(m + 2, sizeof(int));

    for (i = 0 ; i < n + 2 ; i++)
    {
        if (i == 0 || i == n + 1)
            for (j = 0 ; j <= n + 1 ; j++)
                romeo[i][j] = -1, julieta[i][j] = -1;

        else
        {
            romeo[i][0] = -1;
            romeo[i][n + 1] = -1;
            julieta[i][0] = -1;
            julieta[i][n + 1] = -1;
        }
    }

    int *coada = (int*) calloc(2 * 100 * 100 + 1, sizeof(int));
    int elem = 0, nrElem = 0;

    int dx[] = {0,  0, 1, -1, -1, -1,  1, 1};
    int dy[] = {1, -1, 0,  0,  1, -1, -1, 1};

    for (i = 1 ; i <= n ; i++)
    {
        char *sir = (char*) calloc(m, sizeof(char));
        fgets(sir,101,in);
        for (j = 1 ; j <= m ; j++)
        {
            char a = sir[j - 1];

            if (a == 'R')
            {
                coada[nrElem] = 1000000 + i * 1000 + j;
                romeo[i][j] = 1;
                nrElem++;
            }
            if (a == 'J')
            {
                coada[nrElem] = i * 1000 + j;
                julieta[i][j] = 1;
                nrElem++;
            }
            if (a == 'X')
            {
                romeo[i][j] = -1;
                julieta[i][j] = -1;
            }
        }
        free(sir);
    }

    int rezolvat = 0;
    while (elem < nrElem && !rezolvat)
    {
        int rj = 0;
        if (coada[elem] > 1000000)
            rj = 1, coada[elem] -= 1000000;

        int x = coada[elem] / 1000;
        int y = coada[elem] % 1000;

        if (romeo[x][y] == julieta[x][y])
            fprintf(out,"%d %d %d",romeo[x][y],x,y), rezolvat = 1;

        for (i = 0 ; i < 8 ; i++)
        {
            if (romeo[x + dx[i]][y + dy[i]] == 0 && rj)
            {
                romeo[x + dx[i]][y + dy[i]] = romeo[x][y] + 1;
                coada[nrElem] = 1000000 + (x + dx[i]) * 1000 + y + dy[i];
                nrElem++;
            }
            if (julieta[x + dx[i]][y + dy[i]] == 0 && !rj)
            {
                julieta[x + dx[i]][y + dy[i]] = julieta[x][y] + 1;
                coada[nrElem] = (x + dx[i]) * 1000 + y + dy[i];
                nrElem++;
            }
        }
        elem++;
    }
    for (i = 0 ; i < n + 2 ; i++)
        free(romeo[i]), free(julieta[i]);
    free(romeo);
    free(julieta);
    free(coada);

    return 0;
}