IMPA/p985/p985.cpp

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

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 west during phase 0 etc
    E0 is to the east during phase 1, E1 to the north during phase 1 etc
*/

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

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

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;

	ostringstream debug_stream;

    queue<Agent> search_queue;

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

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

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

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

                getline(cin, str_in);

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

                the_matrix[x][y] = (str_in.find('N') != string::npos) ? (1<<NORTH) : 0;
                the_matrix[x][y] |= (str_in.find('E') != string::npos) ? (1<<EAST) : 0;
                the_matrix[x][y] |= (str_in.find('S') != string::npos) ? (1<<SOUTH) : 0;
                the_matrix[x][y] |= (str_in.find('W') != string::npos) ? (1<<WEST) : 0;
            }
        }

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

				int phase = 4;
				if(check_dir(Agent{x,y,phase}, NORTH))
				{
					debug_stream << "Arrow to NORTH" << endl;
				}

				if(check_dir(Agent{x,y,phase}, EAST))
				{
					debug_stream << "Arrow to EAST" << endl;
				}

				if(check_dir(Agent{x,y,phase}, SOUTH))
				{
					debug_stream << "Arrow to SOUTH" << endl;
				}

				if(check_dir(Agent{x,y,phase}, WEST))
				{
					debug_stream << "Arrow to WEST" << endl;
				}
            }
        }

        // Clear queue
		while(!search_queue.empty())
			search_queue.pop();
		
		// 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();

			debug_stream << "Searching [" << smith.x << "][" << smith.y << "] during phase " << smith.steps%4 << " (step " << smith.steps << ")\n";

            if(smith.x == width-1 && smith.y == height-1)
            {
				debug_stream << "Found exit!" << endl;
                steps = smith.steps;
                break;
            }

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

            if(smith.y != 0 && check_dir(smith, NORTH))
            {
				debug_stream << "Possible to go NORTH" << endl;
                search_queue.push(Agent{smith.x,smith.y-1,smith.steps+1});
            }

            if(smith.x != width-1 && check_dir(smith, EAST))
            {
				debug_stream << "Possible to go EAST" << endl;
                search_queue.push(Agent{smith.x+1,smith.y,smith.steps+1});
            }

            if(smith.y != height-1 && check_dir(smith, SOUTH))
            {
				debug_stream << "Possible to go SOUTH" << endl;
                search_queue.push(Agent{smith.x,smith.y+1,smith.steps+1});
            }

            if(smith.x != 0 && check_dir(smith, WEST))
            {
				debug_stream << "Possible to go WEST" << endl;
                search_queue.push(Agent{smith.x-1,smith.y,smith.steps+1});
            }

        }

		if(steps)
			cout << steps << endl;
		else
			cout << "no path to exit" << endl;

    }

    return 0;
}