IMPA/p985/p985.cpp

#include <iostream>
#include <list>
#include <string>
#include <queue>
#include <utility>

using namespace std;



// Serves to keep track of any map, each bit is mapped to something
uint8_t the_matrix[500][500];

/*
V3 V2 V1 V0 E3 E2 E1 E0

Vx: Visited in this phase, V0 is the first phase
Ex: Edge in this direction, E0 is to the north during phase 0, E1 to the east during phase 0 etc
    E0 is to the east during phase 1, E1 to the south during phase 1 etc
*/

struct Agent
{
    int x;
    int y;
    int steps;
};

enum Direction
{
    NORTH,
    EAST,
    SOUTH,
    WEST
};

bool check_dir(Agent smith, Direction dir)
{
    return the_matrix[smith.x][smith.y] & (0x01 << ((dir+smith.steps)%4));
}

int main()
{

    int width, height, steps;
    string str_in;

    queue<Agent> search_queue;

    while(cin >> width >> height)
    {
        steps = 0;

        cin.ignore(1000, '\n');

        cout << "Read width and height [" << width << "][" << height << "]\n";

        for(int x = 0; x < width; x++)
        {
            for(int y = 0; y < height; y++)
            {
                if(x == (width-1) && y == (height-1))
                    continue;

                getline(cin, str_in);

                cout << "Read line: " << str_in << endl;

                the_matrix[x][y] = (str_in.find('N') != string::npos) ? 1 : 0;
                the_matrix[x][y] |= (str_in.find('E') != string::npos) ? 2 : 0;
                the_matrix[x][y] |= (str_in.find('S') != string::npos) ? 4 : 0;
                the_matrix[x][y] |= (str_in.find('W') != string::npos) ? 8 : 0;
            }
        }

        cout << "populated the graph" << endl;
        for(int x = 0; x < width; x++)
        {
            for(int y = 0; y < height; y++)
            {
                cout << x << ", " << y << ": 0x" << std::hex << (int)the_matrix[x][y] << endl;
            }
        }

        // Start in upper right corner
        search_queue.push(Agent{0,0,0});

        // Bredden först
        while(!search_queue.empty())
        {
            Agent smith = search_queue.front();
            search_queue.pop();

            if(smith.x == width-1 && smith.y == height-1)
            {
                steps = smith.steps+1;
                break;
            }

            if(the_matrix[smith.x][smith.y] & (0x10 << ((smith.steps)%4)))
            {
                // Already visited
                continue;
            }

            if(smith.y != 0 && check_dir(smith, NORTH))
            {
                search_queue.push(Agent{smith.x,smith.y-1,smith.steps+1});
            }

            if(smith.x != width-1 && check_dir(smith, EAST))
            {
                search_queue.push(Agent{smith.x,smith.y+1,smith.steps+1});
            }

            if(smith.y != height-1 && check_dir(smith, SOUTH))
            {
                search_queue.push(Agent{smith.x,smith.y+1,smith.steps+1});
            }

            if(smith.x != 0 && check_dir(smith, WEST))
            {
                search_queue.push(Agent{smith.x-1,smith.y,smith.steps+1});
            }

        }

        cout << steps;

    }

    return 0;
}