Cod sursa(job #1096971)

Utilizator dianaa21Diana Pislaru dianaa21 Data 2 februarie 2014 19:54:26
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.36 kb
#include <fstream>
#include <queue>
using namespace std;

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

const int DIM = 101;
struct Bla {int x, y;};
queue <Bla> Q;
Bla aux;

int c[DIM][DIM], n, m, d[DIM][DIM], sr, sj, fr, fj, minim = 999999, sol1, sol2, sol;

int lin[] = {-1,-1,0,1,1,1,0,-1};
int col[] = {0,1,1,1,0,-1,-1,-1};

void Read();
void Lee(int c[DIM][DIM]);
bool OK(int i, int j, int s[DIM][DIM]);

int main()
{
    Read();
    aux.x = sr;
    aux.y = fr;
    Q.push(aux);
    Lee(c);
    aux.x = sj;
    aux.y = fj;
    Q.push(aux);
    Lee(d);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            if (c[i][j] == d[i][j] && c[i][j] > 1)
                if (c[i][j] < minim)
                {
                    minim = c[i][j];
                    sol = minim;
                    sol1 = i;
                    sol2 = j;
                }
    os << sol << ' ' << sol1 << ' ' << sol2;
    return 0;
}

void Read()
{
    char x;
    is >> n >> m;
    is.get();
    for (int i = 1; i <= n; ++i)
    {
        for ( int j = 1; j <= m; ++j)
        {
            is.get(x);
            if ( x == ' ')
            {
                c[i][j] = 0;
                d[i][j] = 0;
            }

            if ( x == 'X')
            {
                c[i][j] = -1;
                d[i][j] = -1;
            }

            if ( x == 'R')
            {
                sr = i;
                fr = j;
                c[i][j] = 1;
            }
            if(x == 'J')
            {
                sj = i;
                fj = j;
                d[i][j] = 1;
            }
        }
        is.get();
    }


}
void Lee(int s[DIM][DIM])
{
    int i, j, vi, vj;
    while (!Q.empty())
    {
        aux = Q.front();
        i = aux.x;
        j = aux.y;
        Q.pop();
        for (int k = 0; k < 8; ++k)
        {
            vi = i + lin[k];
            vj = j + col[k];
            if (OK(vi, vj, s) && s[vi][vj] == 0)
            {
                s[vi][vj] = s[i][j] + 1;
                aux.x = vi;
                aux.y = vj;
                Q.push(aux);
            }
        }
    }

}
bool OK(int i, int j, int s[DIM][DIM])
{
    if ( i < 1 || j < 1 || i > n || j > m)
        return false;
    if (s[i][j] == -1)
        return false;

    return true;
}