Searching an exit in a matrix map using breadth-first search algorithm

Question

I'm trying to solve an online problem about breadth-first search algorithm.

The problem can be resumed as:

Given height and width of a map, read the map where "S" is your initital position, "x" is a wall (you can't go into this position), "." is a free cell, and "T" is where you want to go (the exit). After reading the map, read your life points. For each step given you loose 0.25 of your life points. The answer should be "YES" if you can reach "T" from "S" without having a negative number of life points, and "NO" otherwise.

Some examples:

Input: 1 6
S....T
1

Output: NO

---

Input: 1 6
.S...T
1

Output: YES

---

Input: 10 10
.Sx.x....x
.x..xx...x
...xxxx.x.
.....xx...
.xx......x
..x.....x.
.x.xxx....
...xx..x..
x.x...T.x.
.x.x..x..x
4

Output: YES

I tried coding the algorithm in a lot of different ways to boost performance. The Time Limit of this problem is 6 seconds (sum of all test cases):

My last attempt, which I miserably thought would be faster took 10.0852 seconds, here it is:

#include <iostream>
#include <vector>
#include <deque>
using namespace std;

class Point {
    public:
        int i, j, lifes;
        char c;

    Point() { }
    Point(int i, int j) {
        this->i = i;
        this->j = j;
    }
    Point(int i, int j, char c) {
        this->i = i;
        this->j = j;
        this->c = c;
    }
};

typedef vector<Point> vP;
typedef vector<vP> vvP;
typedef deque<Point> dP;

void push_back_if_reachable(vvP& map, dP& queue, int i, int j, int lifes) {
    if ((map[i][j].c != 'x') && (lifes >= 0)) {
        map[i][j].lifes = lifes;
        queue.push_back(static_cast<Point>(map[i][j]));
    }
}

bool canReachT(vvP& map, dP& queue) {
    dP::iterator p;

    while (!queue.empty()) {
        p = queue.begin();
        queue.pop_front();

        if (p->c == 'T')
            return true;

        p->c = 'x';
        push_back_if_reachable(map, queue, p->i-1, p->j, p->lifes-1); // top
        push_back_if_reachable(map, queue, p->i, p->j+1, p->lifes-1); // right
        push_back_if_reachable(map, queue, p->i+1, p->j, p->lifes-1); // bottom
        push_back_if_reachable(map, queue, p->i, p->j-1, p->lifes-1); // left
    }
    return false;
}

int main() {
    int height, width;
    cin >> height >> width;

    vvP map(height+2, vP(width+2)); //+2 because of borders
    dP queue;

    // read input
    int i, j;
    for (i=1; i<=height; i++) {
        for (j=1; j<=width; j++) {
            map[i][j] = Point(i, j);
            cin >> map[i][j].c;

            if (map[i][j].c == 'S') {
                queue.push_back(static_cast<Point>(map[i][j]));
            }
        }

        // construct left and right borders
        map[i][0] = Point(i, 0, 'x');
        map[i][j] = Point(i, j, 'x');
    }

    // construct top and bottom borders
    for (j=1; j<=width; j++) {
        map[0][j] = Point(0, j, 'x');
        map[i][j] = Point(i, j, 'x');
    }

    int lifes;
    cin >> lifes;
    queue.begin()->lifes = lifes * 4;

    if (canReachT(map, queue))
        cout << "YES\n";
    else
        cout << "NO\n";

    return 0;
}

My best attempt if you want to see (6.0020 seconds) can be found in this Ideone link.

---

Background: I used to code online problems using classic C over 2 years, and I'm trying in the last 3 weeks to learn C++.

Maybe the issue with my code is some C++ standard I'm not aware of. I'm here looking how to improve the performance of my code, and to learn how to write better C++ code.

I don't know if it is against this site rules to link the online question, if it is not I can share the link if you want.

I would be very glad on any advice. Thanks.

EDIT

I have sent 27 submissions in C++, all them failed. I consider this one as my best attempt (6.0026 seconds):

#include <iostream>
#include <vector>
using namespace std;

class Point {
    public:
        char c;
        bool visited;
        int i, j, depth;

    Point () {
        this->visited = false;
    }
};

typedef vector<Point> vP;
typedef vector<vP> vvP;
typedef vector<Point*> queue;

int main() {
    int h, w;
    cin >> h >> w;

    vvP map(h+2, vP(w+2));
    queue BFS;

    int i, j;
    for (i=1; i<=h; i++) {
        for (j=1; j<=w; j++) {
            Point& cell = map[i][j];
            cell.i = i;
            cell.j = j;

            cin >> cell.c;
            if (cell.c == 'S') {
                BFS.emplace_back(&cell);
                cell.visited = true;
                cell.depth = 0;
            }
        }
        map[i][0].visited = map[i][j].visited = true;
    }
    for (j=1; j<=w; j++)
        map[0][j].visited = map[i][j].visited = true;


    int lifes;
    cin >> lifes;
    lifes *= 4;


    int depth;
    int item = 0;
    do {

        Point*& Position = BFS[item++];

        if (Position->c == 'x')
            continue;

        if (Position->c == 'T') {
            cout << "SIM\n";
            return 0;
        }


        depth = Position->depth + 1;
        i = Position->i;
        j = Position->j;

        if (depth <= lifes) {

            Point& North = map[i-1][j];
            Point& East = map[i][j+1];
            Point& South = map[i+1][j];
            Point& West = map[i][j-1];

            if (North.visited == false) {
                BFS.emplace_back(&North);
                North.visited = true;
                North.depth = depth;
            }
            if (East.visited == false) {
                BFS.emplace_back(&East);
                East.visited = true;
                East.depth = depth;
            }
            if (South.visited == false) {
                BFS.emplace_back(&South);
                South.visited = true;
                South.depth = depth;
            }
            if (West.visited == false) {
                BFS.emplace_back(&West);
                West.visited = true;
                West.depth = depth;
            }

        }

    } while (item < BFS.size());

    cout << "NAO\n";
    return 0;
}

Ideone link.

And I doubt I'm able to do something better than that because I have spent more than 24 hours on it.

Well, here are the things I learned so far (maybe wrong):

• BFS algorithm needs an state (true|false or 0|1) to mark a Point as visited. I first thought that by changing a visited cell to a wall-cell (. to x) would be faster, but truly it slows down about 2 seconds (see @juvian's answer explanation).
• The use of references speeds up the performance in about 0.3 seconds. (Ex: Point& North = map[i-1][j];)
• The container <deque> is useless, none of my tries using it was faster than my custom queues.
• My ex-tutor gave me his C answer to this problem (Ideone link, Portuguese-BR, which got accepted with 5.5045 seconds).
• My conclusion: I shouldn't be learning C++. It is impossible to solve it in a C++ way. C will never loose.

Thank you all guys. I really appreciate your time helping me.

Answer 1

The main point about breadth-first search is that when you visit a node, you are visting it with the shortest distance possible. That´s why visiting a node twice does not make sense, as on your second visit you are visiting it with a higher or equal distance.

In your approach, although you are setting your current node as visited using p->c = 'x';, The correct approach is to mark the ones you add to the queue as visited, and not the node that you removed from the queue. Think that until a node is popped from the queue, it is not marked as visited so while it´s true that from the moment it gets popped it won´t get visited again, it´s entirely possible (and highly likely) that your queue has multiple of this same node already stored.

I would remove the line p->c = 'x';, change your push_back_if_reachable:

void push_back_if_reachable(vvP& map, dP& queue, int i, int j, int lifes) {
    if ((map[i][j].c != 'x') && (lifes >= 0) && map[i][j].c != 'v') {
        map[i][j].lifes = lifes;
        map[i][j].c = 'v'; // mark as visited  
        queue.push_back(static_cast<Point>(map[i][j]));
    }
}

And finally after the line queue.begin()->lifes = lifes * 4; add : queue.begin()->c = 'v';