Cod sursa(job #349613)

Utilizator Omega91Nicodei Eduard Omega91 Data 20 septembrie 2009 16:13:42
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.01 kb
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <queue>


class coord {
    public:
    short y, x;
    coord operator+(const coord a)
        { coord aux; aux.x = x + a.x; aux.y = y + a.y; return aux; };
    coord operator=(const coord a)
        { x = a.x; y = a.y; return *this; }
};

short N, M;

const short MASKSZ = 1255, NMAX = 101;

// UniDimensionalTransform
inline short udt(const short i, const short j) { return i * M + j; }

inline bool inlimits(const coord c) { return c.y >= 0 && c.y < N && c.x >= 0 && c.x < M; }

void bset(char bits[], const short& pos)
    { bits[pos >> 3] |= 1 << (pos & 7); }
    
bool btest(const char bits[], const short& pos)
    { return bits[pos >> 3] & 1 << (pos & 7); };

void citire(coord& R, coord& J, char mask[])
{
    short i, j;
    char c;
    std::ifstream f("rj.in");
    f >> N >> M;
    for (i = 0; i != N; ++i, f.ignore())
        for (j = 0; j != M; ++j) {
            f.get(c);
            switch (c) {
                case 'X': bset(mask, udt(i, j)); break;
                case ' ': break;
                case 'R': R.x = j, R.y = i; break;
                case 'J': J.x = j, J.y = i; break;
                default: --j; break; // '\n', '\r' that sort of stuff
            }
        }
    f.close();
}

void fill(const coord sp, const char mask[], short c[][NMAX])
{
    /* y and x, clockwise, starting from North */
    static coord dir[] = {{-1, 0}, {-1, 1}, {0, 1}, {1, 1}, 
                          {1, 0}, {1, -1}, {0, -1}, {-1, -1}};
    char visited[MASKSZ] = {};
    std::queue<coord> q; 
    coord cc, nc;
    q.push(sp);
    bset(visited, udt(sp.y, sp.x));
    do {
        cc = q.front(); q.pop();
        for (int8_t i = 0; i != 8; ++i) {
            nc = cc + dir[i];
            if (inlimits(nc))
                if (  !btest(mask,    udt(nc.y, nc.x)) &&
                      !btest(visited, udt(nc.y, nc.x))   ) {
                    c[nc.y][nc.x] = c[cc.y][cc.x] + 1;
                    bset(visited, udt(nc.y, nc.x));
                    q.push(nc);
                }
        }
    } while(!q.empty());
}

void detpos(short& Tmin, coord& C, const short R[][NMAX], const short J[][NMAX])
{
    short i, j;
    Tmin = NMAX * NMAX;
    for (i = 0; i != N; ++i)
        for (j = 0; j != M; ++j)
            if (R[i][j] && R[i][j] == J[i][j])
                if (R[i][j] < Tmin) Tmin = R[i][j], C.x = j, C.y = i;
    ++Tmin, ++C.x, ++C.y;
}

// used only for debuging purposes
void printmask(const char mask[])
{
    int i, j;
    for (i = 0; i != N; ++i) {
        for (j = 0; j != M; ++j)
            if (btest(mask, udt(i,j))) printf("X");
            else printf(".");
        printf("\n");
    }
}

int main()
{
    coord R, J, meeting;
    char mask[MASKSZ] = {};
    short romp[NMAX][NMAX] = {}, julp[NMAX][NMAX] = {}, Tmin;
    citire(R, J, mask);
    fill(R, mask, romp); fill(J, mask, julp);
    detpos(Tmin, meeting, romp, julp);
    std::ofstream f("rj.out");
    f << Tmin << " " << meeting.y << " " << meeting.x << std::endl;
    f.close();
    return 0;
}