Cod sursa(job #1276806)

Utilizator bciobanuBogdan Ciobanu bciobanu Data 26 noiembrie 2014 21:03:20
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.58 kb
#include <cstdio>
#include <queue>
#define IN "rj.in"
#define OUT "rj.out"
#define MAX 105
#define INF 0x3f3f3f3f
using namespace std;
FILE *in, *out;
const int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1};
const int dy[] = {0, 1, -1, 1, -1, 0, 1, -1};
int N, M, rez = INF, rezx, rezy;
int a[MAX][MAX], lr[MAX][MAX], lj[MAX][MAX];
struct poz
{
    int x, y;
} R, J;
poz make_poz(int a, int b)
{
    poz P;
    P.x = a;
    P.y = b;
    return P;
}
void citire()
{
    char aux[MAX];
    int i, j;
    in = fopen(IN, "r");
    fscanf(in, "%d%d\n", &N, &M);
    for(i = 0; i < N; ++i)
    {
        fgets(aux, MAX, in);
        for(j = 0; j < M; ++j)
        {
            if(aux[j] == 'X')
                a[i][j] = 1;
            else if(aux[j] == 'R')
                R = make_poz(i, j);
            else if(aux[j] == 'J')
                J = make_poz(i, j);
        }
    }
    fclose(in);
}
void lee_romeo()
{
    int i, j, ii, jj, t;
    queue <poz> Q;
    Q.push(R);
    lr[R.x][R.y] = 1;
    do
    {
        i = Q.front().x;
        j = Q.front().y;
        for(t = 0; t < 8; ++t)
        {
            ii = i + dx[t];
            jj = j + dy[t];
            if(ii >= 0 && jj >= 0 && ii < N && jj < M && !a[ii][jj] && ((lr[ii][jj] > lr[i][j] + 1) || (!lr[ii][jj])))
            {
                lr[ii][jj] = lr[i][j] + 1;
                Q.push(make_poz(ii, jj));
            }
        }
        Q.pop();
    }
    while(!Q.empty());
}
void lee_julieta()
{
    int i, j, ii, jj, t;
    queue <poz> Q;
    Q.push(J);
    lj[J.x][J.y] = 1;
    do
    {
        i = Q.front().x;
        j = Q.front().y;
        for(t = 0; t < 8; ++t)
        {
            ii = i + dx[t];
            jj = j + dy[t];
            if(ii >= 0 && jj >= 0 && ii < N && jj < M && !a[ii][jj] && ((lj[ii][jj] > lj[i][j] + 1) || (!lj[ii][jj])))
            {
                lj[ii][jj] = lj[i][j] + 1;
                Q.push(make_poz(ii, jj));
            }
        }
        Q.pop();
    }
    while(!Q.empty());
}
void rezolva()
{
    int i, j;
    lee_romeo();
    lee_julieta();
    for(i = 0; i < N; ++i)
    {
        for(j = 0; j < M; ++j)
        {
            if(lr[i][j] == lj[i][j] && lr[i][j] && rez > lr[i][j])
            {
                rez = lr[i][j];
                rezx = i + 1;
                rezy = j + 1;
            }
        }
    }
}
void afisare()
{
    out = fopen(OUT, "w");
    fprintf(out, "%d %d %d\n", rez, rezx, rezy);
    fclose(out);
}
int main()
{
    citire();
    rezolva();
    afisare();
    return 0;
}