Cod sursa(job #1317164)

Utilizator blackoddAxinie Razvan blackodd Data 14 ianuarie 2015 17:22:30
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.09 kb
#include <fstream>
#include <queue>

using namespace std;

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

#define Dim 160
#define INF 999

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

queue<pair<int,int> >Q;

int n, m, ipoz = INF, jpoz = INF;

char s[150];
int c[Dim][Dim];
int t[Dim][Dim];

void Read();
void Lee();
bool Ok(int i, int j);


int main()
{
    Read();
    Lee();
    fout << c[ipoz][jpoz] << ' ' << ipoz + 1  << ' ' << jpoz + 1;
    fin.close();
    fout.close();
    return 0;
}

void Lee()
{
    int i, j, iv, jv;

    while ( !Q.empty() )
    {
        i = Q.front().first;

        j = Q.front().second;

        Q.pop();

        for ( int d = 0; d < 8; ++d )
        {
            iv = i + di[d];

            jv = j + dj[d];

            if ( Ok( iv, jv ) && c[i][j] + 1 < c[iv][jv] )
            {
                c[iv][jv] = c[i][j] + 1;

                Q.push({ iv, jv });
            }

            else

            if ( Ok( iv, jv ) && c[iv][jv] == c[i][j] + 1 )
            {

                if ( iv < ipoz  )
                {
                    ipoz = iv;

                    jpoz = jv;
                }

                else

                if ( iv == ipoz && jv < jpoz )
                {
                    ipoz = iv;

                    jpoz = jv;
                }

            }
        }
    }
}

bool Ok(int i, int j)
{
    if ( i < 0 or i > n - 1 or j < 0 or j > m - 1 or t[i][j] == -1 )
        return false;
    return true;
}

void Read()
{
    fin >> n >> m;

    fin.get();

    for ( int i = 0; i < n; ++i )
    {

        fin.getline( s, 150, '\n' );

        for ( int j = 0; j < m; ++j )
        {

            if ( s[j] == ' ' )

                t[i][j] = 1;

            if ( s[j] == 'X' )

                t[i][j] = -1;

            c[i][j] = INF;

            if ( s[j] == 'J' || s[j] == 'R' )
            {
                Q.push({i, j});

                c[i][j] = 0;
            }
        }
    }
}