# Time Limit Exceeded in BFS maze solver

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.

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() {
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;
}
• Before it can be optimized for speed, it really needs to be refactored. That should make optimization much easier. – Jamal Jan 9 '14 at 16:22
• @Jamal, I've always had trouble in that! What would you suggest as a good tutorial (or such kind) to properly structure the code? – user2779853 Jan 9 '14 at 16:30
• I do not have anything in mind, but this code can still be reviewed to address code clarity and such. Optimization may still be mentioned, but it depends on what the reviewer wants to say. – Jamal Jan 9 '14 at 16:34
• I've seen it only in one place, but the mantra goes: Prefer begin(v) to v.begin(). A text search on Sutter for "Nonmember begin and end" explains why: The basic rationale is that nonmember begin/end are more extensible. – sturmer May 6 '14 at 13:15

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.

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() {
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 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;
};
// 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();
// By using get_neighbors, we can prevent the repetition
for (const auto& neighbor : get_neighbors(p, maze)) {
cell_search_state& neighbor_state =
search_state[neighbor.row][neighbor.col];
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.

• Excellent, except that you took the refactoring one step too far. Each maze is an independent problem; you read it, solve it, and print the YES or NO result immediately. Repeat that T times. There's no advantage to building a vector of all T mazes. – 200_success Jan 9 '14 at 21:48
• The small advantage is that all information about the input format is limited to read_test_cases. Your approach would require reading in the number of test cases, then calling read_test_case N times, which isn't terrible but is unnecessary. Since the number of test cases is guaranteed not to exceed 20 and the size of each Maze object will be well under 10kB (the exact size depends on the implementation of std::vector<bool>), this use of memory is unimportant and I judge the clarity gained by separation of concerns is worth the cost. – ruds Jan 9 '14 at 21:57

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;
}
• I did use a queue initially. But the Online Judge generated a segmentation fault for no reason when I used it. But when I replaced it with vector, it worked. – user2779853 Jan 10 '14 at 1:33