Cod sursa(job #1125715)

Utilizator stinkyStinky si Grasa stinky Data 26 februarie 2014 19:09:13
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.12 kb
#include <iostream>
#include <fstream>
#include <queue>

using namespace std;

const int N = 105;

const int dlin[] = {-1, -1, -1, 0, 0, 1, 1, 1};
const int dcol[] = {-1, 0, 1, -1, 1, -1, 0, 1};

struct pozitie
{
    short int lin, col;
};

ifstream in("rj.in");
ofstream out("rj.out");

char a[N][N];
short int n, m, rom[N][N], jul[N][N];

queue <pozitie> q;

void citire()
{
    in >> n >> m >> ws;
    for (short int i = 1; i <= n; i++)
        in.getline(1 + a[i], N);
}

void bfs(short int d[N][N], pozitie x)
{
    pozitie y;
    for (short int i = 1; i <= n; i++)
        for (short int j = 1; j <= m; j++)
            d[i][j] = -1;
    q.push(x);
    d[x.lin][x.col] = 0;
    while (!q.empty())
    {
        x = q.front();
        q.pop();
        for (short int i = 0; i < 8; i++)
        {
            y.lin = x.lin + dlin[i];
            y.col = x.col + dcol[i];
            if (a[y.lin][y.col] == ' ' && d[y.lin][y.col] == -1)
            {
                q.push(y);
                d[y.lin][y.col] = 1 + d[x.lin][x.col];
            }
        }
    }
}

void scrie(short int d[N][N])
{
    for (short int i = 1; i <= n; i++)
    {
        for (short int j = 1; j <= m; j++)
            out << d[i][j] << "\t";
        out << "\n";
    }
    out << "\n****\n";
}

void rezolva()
{
    short int i, j, linia, coloana;
    linia = coloana = 0;
    rom[0][0] = 30000;
    for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++)
            if (rom[i][j] == jul [i][j] && rom[i][j] != -1)
                if (rom[i][j] < rom[linia][coloana])
                {
                    linia = i;
                    coloana = j;
                }
    out << 1 + rom[linia][coloana] << " ";
    out << linia << " " << coloana << "\n";
}

int main()
{
    citire();
    for (short int i = 1; i <= n; i++)
        for (short int j = 1; j <= m; j++)
            if (a[i][j] == 'R')
                bfs(rom, (pozitie){i, j});
            else if (a[i][j] == 'J')
                bfs(jul, (pozitie){i, j});
    //scrie(rom);
    //scrie(jul);
    rezolva();
    return 0;
}