Time Limit Exceeded in BFS maze solver

Question

Here's a problem that I tried solving:

Lakshagraha was a house built of lacquer, made by the Kauravas to kill the Pandavas. The Kauravas wanted to burn the house down when the Pandavas were asleep at night. But poor Kauravas – once again they underestimated their cousins. Having been warned of the nefarious plan, the Pandavas had had an underground set of passages built for escape.

The underground rooms and passages were in the form of a n*m grid where every cell is either free or blocked by a pillar. The Pandavas start at a free cell and they need to reach a destination cell(which can be free or blocked).

The following are the allowed valid moves:

Move from an empty cell to another adjacent empty cell. (Cells sharing a common side are considered adjacent).

If an adjacent cell is blocked, then set the edge of the blocked cell on fire.

If two or more (distinct) edges of a blocked cell are set on fire, then the blocking pillar burns down and clears the cell. After the fire, the cell becomes empty.

Initially no edge of any blocked cell is set on fire. Help the Pandavas find whether it is possible to reach the destination (target cell), because they are the good guys.

Input: The first line contains T, the number of test cases. The description of T Test cases follow. The first line of each test case consists of 2 space separated integers n and m, denoting the dimensions of the grid (n x m grid). Each of the following n lines contain m characters each, where the jth character of the ith line denotes the state of the cell located at the jth column of the ith row of the grid. Each cell can either be blocked (denoted by ‘*’), or free (denoted by ‘.’). The next line of each test case consists of 4 space separated integers sx, sy, ex, ey, where (sx, sy) denotes the cell where you are initially located at, and (ex, ey) denotes the destination cell (1 based indices).

Output: For each test case, output a single line containing YES or NO, denoting whether it is possible to reach the destination cell from the given starting cell by making valid moves as described above.

Constraints:

• \$T ≤ 20\$
• \$1 ≤ n\$
• \$m ≤ 500\$
• \$1 ≤ sx\$, \$ex ≤ n\$
• \$1 ≤ sy\$, \$ey ≤ m\$
• The starting cell is always empty.

Sample Input

3
2 3
.*.
... 
1 1 1 3
3 3 
..* 
..*
.*.
2 1 3 3
2 3
.*.
**.
2 3 1 2

Sample Output

YES
YES
NO

Time Limit: 2 sec

Memory Limit: 256 MB

Initially, I used a backtracking approach to solve the problem. Obviously, that was slow and resulted in TLE. Later, I was told that a simple BFS would do. Hence, I just did a simple BFS, starting at the specified point. Whenever I encounter a pillar, I increase its count and see if its more than 1 (The pillar has been visited twice). If so, I push it into the queue and continue the BFS. Still, the code results in TLE. I really don't know how I can optimize this code more!

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
class data
{
        public:
        int count;
        int x;
        int y;
        int flag;
        char value;
}ob;
int main() {
        // your code goes here
        int test;
        scanf("%d",&test);
        int n,m;
        char temp;
        while(test--)
        {
                scanf("%d%d",&n,&m);
                //printf("%d %d",n,m);

                data ar[n][m];
                for(int i=0;i<n;i++)
                {
                        for(int j=0;j<m;j++)
                        {
                            scanf(" %c",&temp);
                            ob.count=0;
                            ob.x = i;
                            ob.y = j;
                            ob.value = temp;
                            ar[i][j] = ob;
                        }
                }
            int sx,sy,ex,ey;
            scanf("%d%d%d%d",&sx,&sy,&ex,&ey);

            vector<data> v;
            sx-=1;
            sy-=1;
            ex-=1;
            ey-=1;
            v.push_back(ar[sx][sy]);
            int x,y;
            while(true)
            {
                    if(v.size()==0)
                    {
                            printf("NO\n");
                            break;
                    }
                    else
                    {

                            ob = v[0];
                            v.erase(v.begin());
                            x = ob.x;
                            y = ob.y;
                            //cout<<"Current : "<<x<< " "<<y<<endl;
                            ar[x][y].flag=1;
                            if(x+1<n)
                            {
                                    if(ar[x+1][y].flag!=1)
                                    {
                                            if(ar[x+1][y].value == '.')
                                            {
                                                    if(x+1 == ex && y == ey)
                                                    {
                                                            printf("YES\n");
                                                            break;
                                                    }
                                                    else
                                                            v.push_back(ar[x+1][y]);
                                            }
                                            else
                                            {
                                                    ar[x+1][y].count+=1;
                                                    if(ar[x+1][y].count>1)
                                                    {
                                                            if(x+1 == ex && y == ey)
                                                            {
                                                                    printf("YES\n");
                                                                    break;
                                                            }
                                                            else
                                                                    v.push_back(ar[x+1][y]);
                                                    }
                                            }
                                    }
                            }
                            if(x-1>=0)
                            {
                                    if(ar[x-1][y].flag!=1)
                                    {
                                            if(ar[x-1][y].value == '.')
                                            {
                                                    if(x-1 == ex && y == ey)
                                                    {
                                                            printf("YES\n");
                                                            break;
                                                    }
                                                    else
                                                            v.push_back(ar[x-1][y]);
                                            }
                                            else
                                            {
                                                    ar[x-1][y].count+=1;
                                                    if(ar[x-1][y].count>1)
                                                    {
                                                            if(x-1 == ex && y == ey)
                                                            {
                                                                    printf("YES\n");
                                                                    break;
                                                            }
                                                            else
                                                                    v.push_back(ar[x-1][y]);
                                                    }
                                            }
                                    }
                            }
                            if(y+1<m)
                            {
                                    if(ar[x][y+1].flag!=1)
                                    {
                                            if(ar[x][y+1].value == '.')
                                            {
                                                    if(x == ex && y+1 == ey)
                                                    {
                                                            printf("YES\n");
                                                            break;
                                                    }
                                                    else
                                                            v.push_back(ar[x][y+1]);
                                            }
                                            else
                                            {
                                                    ar[x][y+1].count+=1;
                                                    if(ar[x][y+1].count>1)
                                                    {
                                                            if(x == ex && y+1 == ey)
                                                            {
                                                                    printf("YES\n");
                                                                    break;
                                                            }
                                                            else
                                                            v.push_back(ar[x][y+1]);
                                                    }
                                            }
                                    }
                            }
                            if(y-1>=0)
                            {
                                    if(ar[x][y-1].flag!=1)
                                    {
                                            if(ar[x][y-1].value == '.')
                                            {
                                                    if(x == ex && y-1 == ey)
                                                    {
                                                            printf("YES\n");
                                                            break;
                                                    }
                                                    else
                                                            v.push_back(ar[x][y-1]);
                                            }
                                            else
                                            {
                                                    ar[x][y-1].count+=1;
                                                    if(ar[x][y-1].count>1)
                                                    {
                                                            if(x == ex && y-1 == ey)
                                                            {
                                                                    printf("YES\n");
                                                                    break;
                                                            }
                                                            else
                                                            v.push_back(ar[x][y-1]);
                                                    }
                                            }
                                    }
                            }
                    }
            }
    }
    return 0;
}

Answer 1

Before I get started, I'm writing C++11. If you're using GCC, you'll need to compile with -std=c++11 (consult your compiler documentation otherwise; if you have to use C++98/03, you'll need to modify some of the code). The code I'm giving you is also untested -- you may need to debug it.

OK, as Jamal mentioned, your first priority is to refactor. If your code isn't organized well, you will have a hard time optimizing it. One way to organize code like this is to write down a set of steps, and then write a function for each step. So let's start with main, and work from there. From a high level, you want to do the following things in your program:

1. Read in the list of mazes from the input.
2. Determine whether each maze can be solved.
3. Output the answers.

Note that I've separated the I/O from the meat of the program. This is good programming practice; it's an example of something called separation of concerns.

This separation will require a good data structure to represent the mazes; we may need to modify the data structure later in order to handle our requirements, but for now let's start with this:

class Maze {
  public:
    struct Point {
        const int row, col;
        Point(int row, int col) : row(row), col(col) {}
    };

    Maze(int num_rows, int num_cols)
        : num_rows(num_rows), num_cols(num_cols),
          starting_point{0, 0}, target{0, 0},
          points(num_rows, std::vector<bool>(num_cols, true)) {
    }

    // The two versions are for convenience.
    bool is_free(int row, int col) const {
        return points[row - 1][col - 1];  // 1-based points, 0-based indices
    }
    bool is_free(const Point& p) const { return is_free(p.row, p.col); }

    int num_rows() const { return num_rows; }
    int num_cols() const { return num_cols; }
    const Point& starting_point() const { return starting_point; }
    const Point& target() const { return target; }

    void set_is_free(int row, int col, bool is_free) {
        points[row - 1][col - 1] = is_free;
    }
    void set_starting_point(const Point& p) {
        starting_point = p;
    }
    void set_target(const Point& p) {
        target = p;
    }

  private:
    const int num_rows, num_cols;
    const Point starting_point, target;
    // points[row][col] is true iff the space in that row and column is free
    std::vector<std::vector<bool>> points;
};

This class should allow us to do what we know we'll need to: construct a maze from input, then later retrieve the parameters of the problem (width, height, starting point, target) and check whether each cell in the maze is free.

You may notice that I spelled it std::vector, not vector; that is because using namespace std; is a bad idea.

OK, so now the main function:

int main() {
    const std::vector<Maze> mazes = read_test_cases();
    for (const auto& maze : mazes) {
        if (solve_maze(maze)) {
            std::printf("YES\n");
        } else {
            std::printf("NO\n");
        }
    }
}

Very simple, no? Now we must write the two functions main requires. First, read_test_cases. Now, you used a lot of scanfs; I won't change that, but consider learning how to use C++'s iostream library. However, I will change the names and structure of the code in order to improve readability.

std::vector<Maze> read_test_cases() {
    std::vector mazes;
    int num_tests;
    std::scanf("%d", &num_tests);
    mazes.reserve(num_tests);
    for (int i = 0; i < num_tests; ++i) {
        int num_rows, num_cols;
        std::scanf("%d%d", &num_rows, &num_cols);
        Maze maze(num_rows, num_cols);
        for (int row = 1; i <= num_rows; ++row) {
            for (int col = 1; j <= num_cols; ++col) {
                char space;
                std::scanf(" %c", &space);
                maze.set_is_free(row, col, space == '.');
            }
        }
        Maze::Point start, target;
        std::scanf("%d%d%d%d", &start.row, &start.col, &target.row, &target.col);
        maze.set_starting_point(start);
        maze.set_target(target);
        mazes.push_back(maze);
    }
    return mazes;
}

OK, now let's get your search algorithm into solve_maze.

bool solve_maze(const Maze& maze) {
    // A bunch of stuff that you had in struct data is now stored in maze.
    struct cell_search_state {
        int num_reachable_walls = 0;
        bool already_visited = false;
    };
    // The array ar that you declared is not standard-compliant C++;
    // arrays must have constant dimensions.
    std::vector<std::vector<cell_search_state>> cell_search_state(
        maze.num_rows(), std::vector<cell_search_state>(maze.num_cols()));
    // You're removing elements from the front of your search queue
    // and adding them to the end; this is inefficient with std::vector.
    // You want to use a queue for your data structure instead.
    //
    // Changing v from a vector to a queue will probably get you a decent
    // speedup by itself.
    std::deque<Maze::Point> search_queue = { maze.get_starting_point() };
    while (!search_queue.empty()) {
        const Maze::Point p = search_queue.front();
        search_queue.pop_front();
        search_state[p.row][p.col].already_visited = true;
        // By using get_neighbors, we can prevent the repetition
        // of code your function had.
        for (const auto& neighbor : get_neighbors(p, maze)) {
            cell_search_state& neighbor_state =
                search_state[neighbor.row][neighbor.col];
            if (neighbor_state.already_visited) continue;
            if (neighbor.is_free()
                    || ++neighbor_state.num_reachable_walls > 1) {
                if (neighbor == maze.get_target())
                    return true;
                search_queue.push_back(neighbor);
            }
        }
    }
    return false;
}

We used the following helpers in that function:

bool operator==(const Maze::Point& l, const Maze::Point& r) {
    return l.col == r.col && l.row == r.row;
}

std::vector<Maze::Point> get_neighbors(const Maze::Point& p, const Maze& m) {
    std::vector neighbors;
    if (p.col < m.num_cols())
        neighbors.emplace_back(p.row, p.col + 1);
    if (1 < p.col)
        neighbors.emplace_back(p.row, p.col - 1);
    if (p.row < m.num_rows())
        neighbors.emplace_back(p.row + 1, p.col);
    if (1 < p.row)
        neighbors.emplace_back(p.row - 1, p.col);
    return neighbors;
}

I think this version of your code will be significantly faster. v.erase(v.begin()) is pretty slow: it requires that you copy the entire contents of the vector (except for the first element, of course). The elements of the search queue and the search_state vector are also smaller -- they have disjoint data now, instead of redundant copies of the data (for instance, each element of v in your code contained a copy of count, flag, and value, even though you only used x and y, and each element of ar contained a copy of x and y, even though they were redundant with the indices.

The bigger benefit, though, is it's much easier for someone to read this code and figure out what's going on! Some of the variables you had (e.g. flag, count) were difficult for me to rename -- until I had rearranged the code as I have it above! And if you hadn't told me you were doing breadth-first search and given me the problem statement, I would have had no idea what all your if (x+1<n) etc. meant. Now a reader can come along and see that we're looking at the neighbors of a point in a maze.

Answer 2

Breadth-first searches are typically implemented using a queue. In fact, that's how you use it: you only ever do v.push_back(…) and v.erase(v.begin()). Therefore, the code would be clearer if you used a std::queue instead of a std::vector. Naming the vector (or queue) v is not helpful; frontier would be a more descriptive term.

while(true) should be avoided if practical, and in this case, it is absolutely practical to do so in the following code:

        while(true)
        {
                if(v.size()==0)
                {
                        printf("NO\n");
                        break;
                }
                else
                {
                        …
                }
        }

What you mean is

    bool path_exists()
    {
        …
        while (frontier.size())
        {
                …
                if (…) return TRUE;
        }
        return FALSE;
    }