OIA N3P3A2010 - Recorriendo el laberinto

#include <iostream>
#include <fstream>
#include <deque>

#define GB(m, x) ((m) &  (1LL<<(x)))
#define SB(m, x) ((m) | (1LL<<(x)))
#define CB(m, x) ((m) &= ~(1LL<<(x)))

using namespace std;

int x[4] = {-1, 1, 0, 0};
int y[4] = {0, 0, -1, 1};
char pa[4] = {'U', 'D', 'L', 'R'};

int d[4000][4000];
int m[4000][4000];
char p[4000][4000];

int bTam, aTam;

struct Par
{
    int primero;
    int segundo;
};

struct Grafo
{
    bool valido(int a, int b)
    {
        return (0 <= a && 0 <= b && a < bTam && b < aTam);
    }

    void bfs(int a, int b)
    {
        deque <Par> cola;
        d[a][b] = 0;
        Par par;
        par.primero = a;
        par.segundo = b;
        cola.push_back(par);
        int e, f;

        int tamCola = 1;
        while(tamCola)
        {
            a = cola.front().primero;
            b = cola.front().segundo;
            cola.pop_front();
            tamCola--;

            for(int i=0; i<4; i++)
            {
                e = a+x[i], f = b+y[i];
                if(valido(e, f)) ///Si es una posición válida
                {
                    if(GB(m[a][b], i)) ///Si puedo ir en esa dirección
                    {
                        if(d[a][b]+1 < d[e][f]) ///Si mejoro la distancia
                        {
                            d[e][f] = d[a][b]+1;
                            p[e][f] = pa[i];
                            par.primero = e;
                            par.segundo = f;
                            cola.push_back(par);
                            tamCola++;
                        }
                    }
                }
            }
        }
    }

    void leer(istream &in, ostream &out)
    {
        int a, b, t, x1, y1, x2, y2;
        in >> a >> b >> t;
        bTam = b, aTam = a;

        for(int i=0; i<b; i++)
            for(int j=0; j<a; j++)
                d[i][j] = 999999999, m[i][j] = 15, p[i][j] = ' ';

        for(int i=0; i<t; i++)
        {
            in >> x1 >> y1 >> x2 >> y2;

            /**
            Los movimientos se describen:
            Si puedo ir U, D, L, o R
            0 bit U
            1 bit D
            2 bit L
            3 bit R

            Si están off, no puedo ir.
            **/

            /**
            ¡Enunciado es garca!
            Las coordenadas pueden estar en orden de der to izq
            Los swap de abajo lo solucionan
            **/

            if(y1 > y2)
                swap(y1, y2);
            if(x1 > x2)
                swap(x1, x2);

            if(x1 == x2) ///Es vertical
            {
                for(int j=y1; j<y2; j++)
                {
                    m[j][x1-1] = CB(m[j][x1-1], 3);
                    m[j][x1+0] = CB(m[j][x1+0], 2);
                }
            }
            else if(y1 == y2) ///Es horizontal
            {
                for(int j=x1; j<x2; j++)
                {
                    m[y1-1][j] = CB(m[y1-1][j], 1);
                    m[y1+0][j] = CB(m[y1+0][j], 0);
                }
            }
        }
        ///Listo, ya tengo todas las restricciones cargadas

        bfs(0, 0);

        if(d[b-1][a-1] == 999999999)
            out << "imposible" << endl;
        else
            out << d[b-1][a-1] << endl;
    }
};

int main()
{
    ifstream in("tabiques.in");
    ofstream out("tabiques.out");

    Grafo g;
    g.leer(in, out);

    in.close();
    out.close();

    return 0;
}