Cod sursa(job #2110330)

Utilizator alexge50alexX AleX alexge50 Data 20 ianuarie 2018 15:57:04
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.49 kb
#include <stdio.h>

#include <queue>

#define MAX_N 100
#define INF ((MAX_N + 2) * (MAX_N + 2))

struct Pos
{
    int m_l, m_c;
    Pos():m_l(0), m_c(0){}
    Pos(int l, int c): m_l(l), m_c(c){}
};

char map[MAX_N + 2][MAX_N + 2];
int  r_dist[MAX_N + 2][MAX_N + 2], j_dist[MAX_N + 2][MAX_N + 2];

void lee(int distmap[MAX_N + 2][MAX_N + 2], Pos p);

int main()
{
    FILE *fin = fopen("rj.in", "r"),
         *fout = fopen("rj.out", "w");
    int n, m;
    Pos pR, pJ, *charToPos[128];

    fscanf(fin, "%d %d" , &n, &m);

    for(int i = 0; i <= n + 1; i++)
        map[i][0] = map[i][m + 1] = 'X';
    for(int j = 0; j <= m + 1; j++)
        map[0][j] = map[n + 1][j] = 'X';

    charToPos['J'] = &pJ;
    charToPos['R'] = &pR;

    fgetc(fin);
    for(int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            map[i][j] = fgetc(fin);
            //printf("%c", map[i][j]);
            if(map[i][j] == 'R' || map[i][j] == 'J')
                *charToPos[map[i][j]] = Pos(i, j);
        }
        fgetc(fin);
        //printf("\n");
    }

    lee(r_dist, pR);
    lee(j_dist, pJ);

    int minT, l, c;

    minT = n * m;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            if(r_dist[i][j] == j_dist[i][j] && r_dist[i][j] != INF && map[i][j] != 'X')
            {
                if(minT > r_dist[i][j])
                {
                    minT = r_dist[i][j];
                    l = i, c = j;
                }
                //printf("%d %d\n", i, j);
            }
            //printf("%d ", j_dist[i][j]);
        }
        //printf("\n");
    }

    fprintf(fout, "%d %d %d", l, c, minT);

    fcloseall();
    return 0;
}

void lee(int distmap[MAX_N + 2][MAX_N + 2], Pos p)
{
    char was[MAX_N + 2][MAX_N + 2];
    char ldir[8] = {0, 0, +1, -1, +1, -1, +1, -1};
    char cdir[8] = {-1, +1, 0, 0, +1, -1, -1, +1};
    std::queue<Pos> q;

    for(int i = 0; i < MAX_N + 2; i++)
        for(int j = 0; j < MAX_N + 2; j++)
            was[i][j] = 0, distmap[i][j] = INF;

    q.push(p);
    was[p.m_l][p.m_c] = 1;
    distmap[p.m_l][p.m_c] = 0;
    while(!q.empty())
    {
        Pos p = q.front();
        q.pop();

        for(int i = 0; i < 8; i++)
        {
            Pos p2 (p.m_l + ldir[i], p.m_c + cdir[i]);
            if(map[p2.m_l][p2.m_c] != 'X' && !was[p2.m_l][p2.m_c])
            {
                was[p2.m_l][p2.m_c] = 1;
                distmap[p2.m_l][p2.m_c] = 1 + distmap[p.m_l][p.m_c];
                q.push(p2);
            }
        }
    }

}