Return to Answer

• 1

• 3.4k
• 17
• 23

• 3.4k
• 17
• 23

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.