Cod sursa(job #961167)

Utilizator primulDarie Sergiu primul Data 11 iunie 2013 18:15:16
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.42 kb
#include <fstream>
#include <iostream>
#include <queue>
#include <deque>
#include <iterator>
#include <algorithm>
 
#define MAXN 102
 
using namespace std;
 
typedef unsigned char uint8;
typedef char int8;
 
char mat[MAXN][MAXN];
short path[2][MAXN][MAXN];
 
struct Coord
{
    Coord() :
        x(0), y(0)
    {}
 
    Coord(int8 xx, int8 yy) :
        x(xx), y(yy)
    {}
 
    int8 x;
    int8 y;
};
 
struct NewCoordIterator
{
    NewCoordIterator(const Coord& coord) :
        m_Dir(0),
        m_Source(coord)
    {}
 
    NewCoordIterator& begin()
    {
        return *this;
    }
 
    NewCoordIterator& end()
    {
        return *this;
    }
 
    Coord operator* ()
    {
        return  Coord(m_Source.x + Directions[m_Dir][0], m_Source.y + Directions[m_Dir][1]);
    }
 
    bool operator != (const NewCoordIterator& rhs) const
    {
        return m_Dir < 8;
    }
 
    const NewCoordIterator& operator ++ ()
    {
        m_Dir++;
        return *this;
    }
 
private:
    uint8 m_Dir;
    Coord m_Source;
     
    static int8 Directions[][2];
};
 
int8 NewCoordIterator::Directions[][2] = { {-1, 0}, {-1, -1}, {0, -1}, {1, -1}, {1, 0}, {1, 1}, {0, 1}, {-1, 1} };
 
Coord posR;
Coord posJ;
 
int main()
{
    int n,m;
    int tmin = MAXN * MAXN + 1;
    Coord meetingPoint(MAXN, MAXN);
    fstream fin("rj.in", fstream::in);
    fstream fout("rj.out", fstream::out);
 
    fin >> n >> m;
    //cout << n << " " << m << endl;
 
    fin.getline(mat[0], MAXN);
 
    for (int i=1; i<=n; ++i)
    {
        fin.getline(mat[i] + 1, MAXN);
        //cout << mat[i] + 1 << endl;
 
        char *ptr;
        if (posR.y == 0)
        {  
            if ((ptr = find(mat[i] + 1,  mat[i] + m + 1, 'R')) < mat[i] + m + 1)
            {
                posR.x = ptr - mat[i];
                posR.y = i;
            }
        }
 
        if (posJ.y == 0)
        {  
            if ((ptr = find(mat[i] + 1, mat[i] + m + 1, 'J')) < mat[i] + m + 1)
            {
                posJ.x = ptr - mat[i];
                posJ.y = i;
            }
        }
    }
 
    //cout << (int)posR.y << " " << (int)posR.x << endl;
    //cout << (int)posJ.y << " " << (int)posJ.x << endl;
 
    /*for (Coord var : NewCoordIterator(Coord(0, 0), Coord(0,0), Coord(n,m)))
    {
        cout << (int)var.x << " " << (int)var.y << endl;
    }
    cout << endl;*/
 
    queue<Coord> Q[2] = { queue<Coord>(deque<Coord>(1, posR)), queue<Coord>(deque<Coord>(1, posJ)) };
     
    int current = 0;
     
    path[0][posR.y][posR.x] = 1;
    path[1][posJ.y][posJ.x] = 1;
     
    Coord lowerBound(1,1), upperBound(m,n);
 
    while (!Q[0].empty() || !Q[1].empty())
    {
        if (!Q[current].empty())
        {
            for (Coord var : NewCoordIterator(Q[current].front()))
            {  
                if (var.x < lowerBound.x or var.x > upperBound.x or
                    var.y < lowerBound.y or var.y > upperBound.y)
                {
                    continue;
                }
             
                if (mat[var.y][var.x] == ' ' and
                    path[current][var.y][var.x] == 0 and
                    ((path[current][Q[current].front().y][Q[current].front().x] + 1 <= path[!current][var.y][var.x]) or path[!current][var.y][var.x] == 0)
                   )
                {
                    //cout << current << " -- " << (int)var.x << " " << (int)var.y << endl;
 
                    path[current][var.y][var.x] = path[current][Q[current].front().y][Q[current].front().x] + 1;
 
                    if (path[current][var.y][var.x] == path[!current][var.y][var.x])
                    {
                        if (path[current][var.y][var.x] < tmin)
                        {
                            tmin = path[current][var.y][var.x];
                            meetingPoint = var;
                        }
                        else if (path[current][var.y][var.x] == tmin)
                        {
                            if (var.y < meetingPoint.y)
                            {
                                meetingPoint = var;
                            }
                            else if (var.y == meetingPoint.y)
                            {
                                if (var.x < meetingPoint.x)
                                {
                                    meetingPoint = var;
                                }
                            }
                        }
                    }
                    else
                    {
                        Q[current].push(var);
                    }
                }
            }
 
            Q[current].pop();
        }
 
        current = !current;
 
        /*ostream_iterator<short> itOut(cout, " ");
        for (int i=1; i<=n; ++i)
        {
            copy_n(path[0][i] + 1, m, itOut);
            cout << endl;
        }
        cout << endl << endl;
        getchar();*/
    }
 
    /*ostream_iterator<short> itOut(cout, " ");
    for (int i=1; i<=n; ++i)
    {
        copy_n(path[0][i] + 1, m, itOut);
        cout << endl;
    }
    cout << endl << endl;
     
    for (int i=1; i<=n; ++i)
    {
        copy_n(path[1][i] + 1, m, itOut);
        cout << endl;
    }
    cout << endl;*/
     
    fout << tmin << " " << (int)meetingPoint.y << " " << (int)meetingPoint.x << "\n";
 
    return 0;
}