Cod sursa(job #955943)

Utilizator claudiumihailClaudiu Mihail claudiumihail Data 1 iunie 2013 22:06:27
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.2 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, const Coord LowerBound, const Coord UpperBound) :
        m_Dir(0),
        m_LowerBound(LowerBound),
        m_UpperBound(UpperBound),
        m_Source(coord)
    {}

    NewCoordIterator& begin()
    {
        return *this;
    }

    NewCoordIterator& end()
    {
        return *this;
    }

    Coord operator* ()
    {
        Coord newCoord(m_Source.x + Directions[m_Dir][0], m_Source.y + Directions[m_Dir][1]);
        
        while (newCoord.x < m_LowerBound.x or newCoord.x > m_UpperBound.x &&
               newCoord.y < m_LowerBound.y or newCoord.y > m_UpperBound.y)
        {
            m_Dir++;
            newCoord = Coord(m_Source.x + Directions[m_Dir][0], m_Source.y + Directions[m_Dir][1]);
        }
        
        return newCoord;
    }

    bool operator != (const NewCoordIterator& rhs) const
    {
        return m_Dir < 8;
    }

    const NewCoordIterator& operator ++ ()
    {
        m_Dir++;
        return *this;
    }

private:
    uint8 m_Dir;
    Coord m_LowerBound;
    Coord m_UpperBound;
    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] + n + 1, 'R')) < mat[i] + n + 1)
            {
                posR.x = ptr - mat[i];
                posR.y = i;
            }
        }

        if (posJ.y == 0)
        {   
            if ((ptr = find(mat[i] + 1, mat[i] + n + 1, 'J')) < mat[i] + n + 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;

    while (!Q[0].empty() || !Q[1].empty())
    {
        if (!Q[current].empty())
        {
            for (Coord var : NewCoordIterator(Q[current].front(), Coord(1,1), Coord(n,m)))
            {
                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;
                    Q[current].push(var);
                    
                    if (path[current][Q[current].front().y][Q[current].front().x] + 1 == 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.x < meetingPoint.x)
                            {
                                tmin = path[!current][var.y][var.x];
                                meetingPoint = 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;
    
    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;
}