Cod sursa(job #1366846)

Utilizator alexandru.ghergutAlexandru-Gabriel Ghergut alexandru.ghergut Data 1 martie 2015 14:08:27
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.36 kb
#include <fstream>
#include <queue>
#include <cstring>
using namespace std;

void BFS(char a[][102], int dist[][102], int start[], int N, int M);
void printResult(int Julieta[][102], int Romeo[][102], int N, int M);

int main()
{
    int N, M, i, j, R[2], J[2];
    ifstream f("rj.in");
    f >> N >> M;
    f.get();

    char a[N + 2][102];
    int Romeo[N + 1][102], Julieta[N + 1][102];
    J[0] = R[0] = -1;

    for (i = 1; i <= N; i++)
    {
        a[i][0] = ' ';
        f.getline(a[i] + 1, 101);
        for (j = 1; j < strlen(a[i]) && (J[0] == -1 || R[0] == -1); j++)
            if (a[i][j] == 'J')
                J[0] = i, J[1] = j;
            else if (a[i][j] == 'R')
                R[0] = i, R[1] = j;
    }
    f.close();

    for (j = 0; j <= M + 1; j++)
        a[0][j] = a[N + 1][j] = 'X';
    for (i = 0; i <= N + 1; i++)
        a[i][0] = a[i][M + 1] = 'X';

    BFS(a, Julieta, J, N, M);
    BFS(a, Romeo, R, N, M);

    printResult(Julieta, Romeo, N, M);
    return 0;
}

void BFS(char a[][102], int dist[][102], int start[], int N, int M)
{
    int neighborX[] = {1, 1, 0, -1, -1, -1, 0, 1};
    int neighborY[] = {0, -1, -1, -1, 0, 1, 1, 1};

    int lin, col, i, j, cLin, cCol;
    for (i = 1; i <= N; i++)
        for (j = 1; j <= M; j++)
            dist[i][j] = 0;

    queue<int> q;
    q.push(start[0]);
    q.push(start[1]);
    dist[start[0]][start[1]] = 1;
    while (!q.empty())
    {
        lin = q.front(), q.pop();
        col = q.front(), q.pop();


        for (i = 0; i <= 7; i++)
        {
            cLin = lin + neighborX[i];
            cCol = col + neighborY[i];
            if (a[cLin][cCol] == ' ' && !dist[cLin][cCol])
            {
                q.push(cLin);
                q.push(cCol);
                dist[cLin][cCol] = dist[lin][col] + 1;
            }
        }
    }
}

void printResult(int Julieta[][102], int Romeo[][102], int N, int M)
{
    int min = 100 * 100 + 1, minLin = -1, maxCol = -1, i, j;
    for (i = 1; i <= N; i++)
        for (j = 1; j <= M; j++)
            if (Julieta[i][j] && Julieta[i][j] == Romeo[i][j])
            {
                if (Julieta[i][j] < min)
                {
                    min = Julieta[i][j];
                    minLin = i;
                    maxCol = j;
                }
            }

    ofstream g("rj.out");
    g << Julieta[minLin][maxCol] << " " << minLin << " " << maxCol;
    g.close();
}