Cod sursa(job #1170822)

Utilizator tatianazTatiana Zapirtan tatianaz Data 14 aprilie 2014 17:35:57
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.99 kb
#include <fstream>
#include <queue>
#include <iomanip>
using namespace std;

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

#define INF 0x3f3f3f3f

const int di[] = { -1, -1, 0, 1, 1, 1, 0, -1};
const int dj[] = { 0, 1, 1, 1, 0, -1, -1, -1};

queue<pair<int, int> > Q;

char c[101];
int R[101][101], J[101][101];
int n, m;
int iv, jv;
int i, j;
int iR, jR, iJ, jJ;

void Lee(int c[101][101], int ip, int jp);
bool Inside(int c[101][101], int x, int y);

int main()
{
    is >> n >> m;
    is.get();
    for ( i = 1; i <= n; ++i )
    {
        is.getline(c, 150);
        for ( j = 1; j <= m; ++j )
        {
            if ( c[j-1] == 'R' )  iR = i, jR = j, R[iR][jR] = 1;
            if ( c[j-1] == 'J' )  iJ = i, jJ = j, J[iJ][jJ] = 1;
            if ( c[j-1] == 'X' )  R[i][j] = -1, J[i][j] = -1;
        }
    }

    Lee(R, iR, jR);
    Lee(J, iJ, jJ);

    int tmin = INF, isos, jsos;

    for ( int i = 1; i <= n; ++i )
        for ( int j = 1; j <= m; ++j )
            if ( R[i][j] != -1 && J[i][j] != -1 && R[i][j] != 0 && J[i][j] != 0)
                if ( R[i][j] == J[i][j] )
                    if ( R[i][j] < tmin )
                    {
                        tmin = R[i][j];
                        isos = i;
                        jsos = j;
                    }

    os << tmin << ' ' << isos << ' ' << jsos;

    is.close();
    os.close();
    return 0;
}

void Lee(int c[101][101], int ip, int jp)
{
    Q.push(make_pair(ip, jp));
    while ( !Q.empty() )
    {
        i = Q.front().first, j = Q.front().second;
        Q.pop();
        for ( int dir = 0; dir < 8; ++dir )
        {
            iv = i + di[dir];
            jv = j + dj[dir];
            if ( Inside(c, iv, jv) && c[iv][jv] == 0 )
            {
                c[iv][jv] = c[i][j] + 1;
                Q.push(make_pair(iv, jv));
            }

        }
    }

}

bool Inside(int c[101][101], int x, int y)
{
    return x >= 1 && y >= 1 && x <= n && y <= m;
}