Cod sursa(job #615518)

Utilizator RarRaresNedelcu Rares RarRares Data 9 octombrie 2011 21:50:09
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.82 kb
#include <iostream>
#include <cstdio>
#include <iomanip>
using namespace std;

struct matrice
{
    short r, j;
};
short   di[8] = {-1, 0, 1, 1, 1, 0, -1, -1},
        dj[8] = {-1, -1, -1, 0, 1, 1, 1, 0};

matrice ORAS[110][110], Qi[3000000], Qj[3000000];
short xr, xj, yr, yj, ok = 0, lmin = 421, xmin = 312, ymin = 123;
int pqr = 0, pqj = 0, uqr = 1, uqj = 1;
int main()
{
    freopen("rj.in", "r", stdin);
    freopen("rj.out", "w", stdout);
    short m, n;
    cin >> n >> m;cin.get();
    for(int i = 0; i < n; i++)
        {
                char aux[100];
                cin.getline(aux, m+1);
                for(int j = 0; j < m; j++)
                switch(aux[j])
                {
                    case 'X':ORAS[i][j].r = ORAS[i][j].j = -1;break;
                    case ' ':ORAS[i][j].r = ORAS[i][j].j = 0;break;
                    case 'R':ORAS[i][j].r = 1;Qi[0].r = i;Qj[0].r = j;break;
                    case 'J':ORAS[i][j].j = 1;Qi[0].j = i;Qj[0].j = j;break;
                }
        }
    while(pqr <= uqr && pqj <= uqj && !ok)
    {
        xr = Qi[pqr].r;
        yr = Qj[pqr].r;
        xj = Qi[pqj].j;
        yj = Qj[pqj].j;
        pqr++;pqj++;
        for(int it = 0; it < 8; it++)
            {
                /**R*/
                if(ORAS[xr][yr].r == ORAS[xr][yr].j)
                    {
                        ok = 1;lmin = ORAS[xr][yr].r;xmin = xr;ymin = yr;break;
                    }
                else
                if(xr + di[it] >= 0 && yr + dj[it] >= 0 && xr + di[it] < n && yr+dj[it] < m && ORAS[xr+di[it]][yr+dj[it]].r != -1)
                    if(!ORAS[xr+di[it]][yr+dj[it]].r)
                    {
                        ORAS[xr+di[it]][yr+dj[it]].r = ORAS[xr][yr].r + 1;
                        Qi[uqr].r = xr + di[it];
                        Qj[uqr].r = yr + dj[it];
                        uqr++;
                    }
                /**J*/
                if(ORAS[xj][yj].r == ORAS[xj][yj].j)
                    {
                        ok = 1;lmin = ORAS[xj][yj].j;xmin = xj;ymin = yj;break;
                    }
                else
                if(xj + di[it] >= 0 && yj + dj[it] >= 0 && xj + di[it] < n && yj+dj[it] < m && ORAS[xj+di[it]][yj+dj[it]].j != -1)
                    if(!ORAS[xj+di[it]][yj+dj[it]].j)
                    {
                        ORAS[xj+di[it]][yj+dj[it]].j = ORAS[xj][yj].j + 1;
                        Qi[uqj].j = xj + di[it];
                        Qj[uqj].j = yj + dj[it];
                        uqj++;
                    }
            }
    }
         for(int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
                cout << ORAS[i][j].r << setw(4);
            cout << '\n';
        }

    cout << xmin+1 << ' ' << ymin+1 << ' ' << lmin;

    return 0;
}