Good day to ya'll. I had this programming excericise of mine where I had to find the shortest path to an exit in an NxM -grid maze in under a second (both N and M would be anywhere between 3 and 1000). The program would be tested with 10 different inputs (mazes), all of which includes a very different amount of exits.

The input goes as follows:

7 10
##########
#.....#... <- exit
#.#.###.##
#..X..#..#
#.#.#.#.##
#......... <- exit
###.######
   ^exit

Where the first number is height and the second width. The rest is the maze itself, and X marks the (starting) spot.

Well, I solved the problem using the A* algorithm and at the same time keeping track of the nearest exit (simple manhattan distance). Now what's bugging me is that my fellow programmers have come to a lot faster and more memory-friendly solutions than I. My request is that you guys point out anything that comes to your mind, were it to be a completely different algorithm or just a stupid memory leak.

Here's the code:

#include <iostream>
#include <vector>
#include <algorithm>

typedef std::vector<int> monovector;
typedef std::vector< std::vector<int> > bivector;

int _abs(int num);
int* get_nearest_goal(int y, int x, bivector &goals_t);
int goals = 0;

void appendClosedList(int y, int x, bivector &openList, bivector &closedList) {
    for(size_t i = 0; i < openList.size(); i++)
        if(openList[i][0] == y && openList[i][1] == x) closedList.push_back(openList[i]);
}

void dropOpenList(int y, int x, bivector &openList) {
    for(size_t i = 0; i < openList.size(); i++)
        if(openList[i][0] == y && openList[i][1] == x) openList.erase(openList.begin()+i);
}

int* get_coords(bivector &openList)
{
    int* coords = new int[2];
    int min_element = 1000000;
    for(size_t i = 0; i < openList.size(); i++) {
        if(openList[i][2] < min_element) {
            min_element = openList[i][2];
            coords[0] = openList[i][0];
            coords[1] = openList[i][1];
        }
    }
    return coords;
}

struct laby_t {
    int h, w, s_y, s_x;
    char **m_layout;
    int ***m_attr, ***_m_attr;
    int ***m_parent, ***_m_parent;

    laby_t() {
        std::cin >> h >> w;

        m_layout  = new char *[h+1];
        for (int i = 0; i < h+1; i++)
            m_layout[i]  = new char[w+1];

        m_parent = new int **[h];
        m_attr  = new int **[h];
        for (int i = 0; i < h; i++) {
            m_attr[i]  = new int *[w];
            m_parent[i] = new int *[w];

            std::cin >> m_layout[i];

            for (int j = 0; j < w; j++) {
                m_attr[i][j] = new int[4];
                m_parent[i][j] = new int[2];

                m_attr[i][j][0] = 0;
                m_attr[i][j][1] = 0;
                m_parent[i][j][0] = 0;
                m_parent[i][j][1] = 0;
                if(m_layout[i][j] == '#') m_attr[i][j][0] = 2;
                if(m_layout[i][j] == 'X') { s_y = i; s_x = j; }
            }
        }

    }

    int get_visited (int y, int x) { return this->m_attr[y][x][0]; }
    int get_depth(int y, int x)    {
        if(this->m_attr[y][x][1]) return this->m_attr[y][x][1];
        else return 0;
    }
    int get_estimate(int y, int x) { return this->m_attr[y][x][2]; }
    int get_priority(int y, int x) { return this->m_attr[y][x][3]; }

    void set_visited(int py, int px, int y, int x, int f_y, int f_x, int depth)  {
        this->m_attr[y][x][0] = 1; 
        this->m_attr[y][x][1] = depth;
        this->m_attr[y][x][2] = _abs(f_y - y) + _abs(f_x - x);
        this->m_attr[y][x][3] = this->m_attr[y][x][1] + this->m_attr[y][x][2];
        this->m_parent[y][x][0] = py;
        this->m_parent[y][x][1] = px;
    }

    void reset()
    {
        delete this->m_attr;
        delete this->m_parent;
        delete this->m_layout;
    }
};

void dropGoals(int f_y, int f_x, bivector &goals_t, laby_t &laby)
{
    for(size_t i = 0; i < goals_t.size(); i++)
        if(goals_t[i][0] == f_y && goals_t[i][1] == f_x) {
            goals_t.erase(goals_t.begin()+i);
            laby.m_layout[goals_t[i][0]][goals_t[i][i]] = '#';
            laby.m_attr[goals_t[i][0]][goals_t[i][i]][0] = 2;
        }
}

int wander(int y, int x, int f_y, int f_x, laby_t &laby, bivector goals_t)
{
    int depth = 1;
    laby.set_visited(y, x, y, x, f_y, f_x, depth);
    monovector r; r.push_back(y); r.push_back(x); r.push_back(laby.get_priority(y, x)); r.push_back(0);
    bivector openList, closedList;
    openList.push_back(r);
    r.clear();

    int dir[4][2] = {
                        { 1, 0},
                        {-1, 0},
                        { 0, 1},
                        { 0,-1}
                    };

    while(!(y == f_y && x == f_x))
    {
        for(int i = 0; i < 4; i++)
        {
            int _y = y + dir[i][0];
            int _x = x + dir[i][1];
            if(y > 0 && y < laby.h-1 && x > 0 && x < laby.w-1) {
                if(
                    (
                        (laby.get_visited(_y, _x) == 0) ||
                        (laby.get_visited(_y, _x) == 1 && laby.get_depth(y, x)+1 < laby.get_depth(_y, _x))
                    )
                  )
                {
                    laby.set_visited(y, x, _y, _x, f_y, f_x, laby.get_depth(y, x)+1);
                    monovector r; r.push_back(_y); r.push_back(_x); r.push_back(laby.get_priority(_y, _x));
                    openList.push_back(r);
                    r.clear();

                    if((_y == 0 || _y == laby.h-1 || _x == 0 || _x == laby.w-1) && (_y != f_y || _x != f_x)) {
                        int d = laby.get_depth(_y, _x);
                        openList.clear();
                        closedList.clear();
                        laby.reset();
                        return d;
                    }
                }
            }
            else { return laby.get_depth(y, x); };
        }

        appendClosedList(y, x, openList, closedList);
        dropOpenList(y, x, openList);

        int *yx = get_coords(openList);
        y = yx[0];
        x = yx[1];

        yx = get_nearest_goal(y, x, goals_t);
        f_y = yx[0];
        f_x = yx[1];

        delete yx;

    }
    int d = laby.get_depth(y, x);
    openList.clear();
    closedList.clear();
    laby.reset();
    return d;
}

int _abs(int num)
{
    if(num <= 0) return -num;
    else return num;
}

int* get_nearest_goal(int y, int x, bivector &goals_t)
{
    int min_dist = 1000000;
    int *f_coords = new int[2];
    for(size_t i = 1; i < goals_t.size(); i++) {
        if(_abs(y - goals_t[i][0]) + _abs(x - goals_t[i][1]) < min_dist) {
            min_dist = _abs(y - goals_t[i][0]) + _abs(x - goals_t[i][1]);
            f_coords[0] = goals_t[i][0];
            f_coords[1] = goals_t[i][1];
        }
    }

    return f_coords;
}

int* get_goals(int &goals, bivector &goals_t, laby_t &laby)
{
    for(int i = 1; i < laby.h - 1; i++) {
        if(laby.m_layout[i][0] == '.') {
            goals++;
            monovector t; t.push_back(i); t.push_back(0); goals_t.push_back(t);
            t.clear();
        }
        if(laby.m_layout[i][laby.w - 1] == '.') {
            goals++;
            monovector t; t.push_back(i); t.push_back(laby.w - 1); goals_t.push_back(t);
            t.clear();
        }
    }

    for(int i = 1; i < laby.w - 1; i++) {
        if(laby.m_layout[0][i] == '.') {
            goals++;
            monovector t; t.push_back(0); t.push_back(i); goals_t.push_back(t);
            t.clear();
        }
        if(laby.m_layout[laby.h - 1][i] == '.') {
            goals++;
            monovector t; t.push_back(laby.h - 1); t.push_back(i); goals_t.push_back(t);
            t.clear();
        }
    }

    return get_nearest_goal(laby.s_y, laby.s_x, goals_t);
}

int main()
{
    int *f_coords = new int[2];
    bivector goals_t;
    laby_t laby;

    f_coords = get_goals(goals, goals_t, laby);

    int min_path = wander(laby.s_y, laby.s_x, f_coords[0], f_coords[1], laby, goals_t);

    delete f_coords;

    std::cout << min_path << std::endl;
    //system("pause");
    return 0;
}

I was too lazy to add comments, so tell me if they are needed.