Cod sursa(job #2138810)

Utilizator MelacasKorian Ebraahim Melacas Data 21 februarie 2018 21:30:40
Problema Rj Scor 50
Compilator c Status done
Runda Arhiva de probleme Marime 3.26 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 < m + 2 ; j++)
                romeo[i][j] = -1, julieta[i][j] = -1;

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

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

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

    for (i = 1 ; i <= n ; i++)
    {
        char *sir = (char*) malloc((m + 2) * sizeof(char));
        fgets(sir,m + 2,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);
    }

    // Se cere prima pozitie din punctul de vedere al liniei si al coloanei
    //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++;
    }

    int timp = 20000, x = 0, y = 0;
    for (i = 1 ; i <= n ; i++)
        for (j = 1 ; j <= m ; j++)
            if (romeo[i][j] != -1 && romeo[i][j] == julieta[i][j] && romeo[i][j] < timp)
            {
                timp = romeo[i][j];
                x = i;
                y = j;
            }

    fprintf(out,"%d %d %d",timp,x,y);

    for (i = 0 ; i < n + 2 ; i++)
        free(romeo[i]), free(julieta[i]);
    free(romeo);
    free(julieta);
    free(coada);

    return 0;
}