Elysian Shadows

Code: Select all

#include <iostream>
#include <vector>


using namespace std;

 char maze[10][10] = {
        {'X', 'X', 'S', 'X', 'X', 'X', 'X', 'X', 'X', 'X'},
        {'X', 'X', 'O', 'X', 'X', 'X', 'X', 'X', 'X', 'X'},
        {'X', 'X', 'O', 'O', 'O', 'O', 'O', 'X', 'X', 'X'},
        {'X', 'X', 'O', 'X', 'X', 'X', 'X', 'O', 'O', 'X'},
        {'X', 'X', 'O', 'O', 'O', 'O', 'X', 'X', 'X', 'X'},
        {'X', 'X', 'X', 'X', 'X', 'O', 'X', 'X', 'X', 'X'},
        {'X', 'X', 'X', 'X', 'X', 'O', 'X', 'X', 'X', 'X'},
        {'X', 'X', 'X', 'O', 'O', 'O', 'O', 'O', 'X', 'X'},
        {'X', 'X', 'X', 'O', 'X', 'X', 'X', 'O', 'X', 'X'},
        {'X', 'X', 'X', 'X', 'X', 'X', 'X', 'E', 'X', 'X'}};

template <typename T, size_t N>
char (&array(T(&)[N]))[N];

struct Point {
    int x;
    int y;

    Point(int x, int y) : x(x), y(y) {}
};

bool contains(vector<Point> v, Point point) {
    for(int i = 0; i < v.size(); i++) {
        if(v[i].x == point.x && v[i].y == point.y) {
            return true;
        }
    }
    return false;
}


bool step(Point start, Point finish, vector<Point> v) {
    if(start.x < 0 || start.x >= sizeof array(maze[0]) 
    || start.y < 0 || start.y >= sizeof array(maze) 
    || maze[start.y][start.x] == 'X') {
        return false;
    }

    v.push_back(start);

    if(start.x == finish.x && start.y == finish.y) {
        cout << "Path:";
        for(int i = 0; i < v.size(); i++) {
            cout << " (" <<  v[i].x << ", " << v[i].y << ")";
        }
        cout << endl;
        return true;
    }

    Point up(start.x, start.y-1);
    Point down(start.x, start.y+1);
    Point left(start.x-1, start.y);
    Point right(start.x+1, start.y);

    bool b;

    if(!contains(v, up)) b = step(up, finish, v);
    if(!contains(v, down)) b |= step(down, finish, v);
    if(!contains(v, left)) b |= step(left, finish, v);
    if(!contains(v, right)) b |= step(right, finish, v);

    return b;
}

int main() {
    step(Point(2, 0), Point(7, 9), vector<Point>());
    return 0;
}