Cod sursa(job #1734866)

Utilizator PaulTPaul Tirlisan PaulT Data 28 iulie 2016 14:06:13
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.35 kb
#include <fstream>
using namespace std;

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

int R[105][105], J[105][105];
int di[] = { -1, -1, -1, 0, 1, 1, 1, 0 };
int dj[] = { -1, 0, 1, 1, 1, 0, -1, -1 };

struct {
    int i, j;
} sti[10100];

int main()
{
    int N, M, ir, jr, ij, jj, tmin = 1000000, isol = 1000000, jsol = 1000000;
    fin >> N >> M;
    fin.get();
    for (int i = 0; i <= N + 1; i++)
        R[i][0] = R[i][M + 1] = J[i][0] = J[i][M + 1] = -1;
    for (int j = 0; j <= M + 1; j++)
        R[0][j] = R[N + 1][j] = J[0][j] = J[N + 1][j] = -1;
    char s[110];
    for (int i = 1; i <= N; i++)
    {
        fin.getline(s, 101);
        for (int j = 1; j <= M; j++)
        {
            if ( s[j - 1] == 'R' )
            {
                ir = i;
                jr = j;
                R[ir][jr] = 1;
            }
            if ( s[j - 1] == 'J' )
            {
                ij = i;
                jj = j;
                J[ij][jj] = 1;
            }
            if ( s[j - 1] == 'X' )
            {
                R[i][j] = J[i][j] = -1;
            }
        }
    }
    int st = 0, dr = 0;
    sti[st].i = ir;
    sti[st].j = jr;
    while ( st <= dr )
    {
        int x = sti[st].i;
        int y = sti[st].j;
        for (int d = 0; d < 8; d++)
        {
            int iv = x + di[d];
            int jv = y + dj[d];
            if ( !R[iv][jv] )
            {
                R[iv][jv] = R[x][y] + 1;
                dr++;
                sti[dr].i = iv;
                sti[dr].j = jv;
            }
        }
        st++;
    }
    st = 0;
    dr = 0;
    sti[st].i = ij;
    sti[st].j = jj;
    while ( st <= dr )
    {
        int x = sti[st].i;
        int y = sti[st].j;
        if ( J[x][y] == R[x][y] )
            if ( tmin > R[x][y] || (tmin == R[x][y] && x < isol) || (tmin == R[x][y] && x == isol && y < jsol) )
            {
                tmin = R[x][y];
                isol = x;
                jsol = y;
            }
        for (int d = 0; d < 8; d++)
        {
            int iv = x + di[d];
            int jv = y + dj[d];
            if ( !J[iv][jv] )
            {
                J[iv][jv] = J[x][y] + 1;
                dr++;
                sti[dr].i = iv;
                sti[dr].j = jv;
            }
        }
        st++;
    }

    fout << tmin << ' ' << isol << ' ' << jsol << '\n';

    fin.close();
    fout.close();
    return 0;
}