A3.cpp

#include "Maze.hpp" #include "a3.hpp"

#include #include

int main(int argc, char* argv[]) { if (argc != 8) { std::cout

// get input parameters int n = std::atoi(argv[1]); int m = std::atoi(argv[2]);

int sx = std::atoi(argv[3]); int sy = std::atoi(argv[4]); int fx = std::atoi(argv[5]); int fy = std::atoi(argv[6]);

std::string name = argv[7];

if ((n

// ream the maze Maze M(n, m);

if (!M.read(name)) { std::cout

// HERE YOUR FUNCTION IS INVOKED int d = distance(M, sx, sy, fx, fy);

// print result std::cout

return 0; } // main

Maze.hpp

#ifndef MAZE_HPP #define MAZE_HPP

#include #include #include #include

class Maze { public: explicit Maze(int n = 0, int m = 0) : n_(n), m_(m), board_(n * m) { }

/** Returns number of rows. */ int nrow() const { return n_; }

/** Returns number of columns. */ int ncol() const { return m_; }

/** Returns true if position (x,y) has been marked as visited before. */ bool is_visited(int x, int y) const { if ((x > -1) && (x -1) && (y

/** Returns true if position (x,y) is open and can be visited. */ bool is_open(int x, int y) const { if ((x > -1) && (x -1) && (y

/** Marks position (x,y) as visited. */ void mark(int x, int y) { if ((x > -1) && (x -1) && (y

/** Marks position (x,y) as not visited. */ void unmark(int x, int y) { if ((x > -1) && (x -1) && (y

/** Reads maze map from a file "name". * Returns true on success. */ bool read(const std::string& name) { std::ifstream f(name.c_str()); if (!f) return false;

std::fill(board_.begin(), board_.end(), 0); std::string buf;

for (int i = 0; i

return true; } // read

private: int n_; int m_; std::vector board_;

}; // class Maze

#endif // MAZE_HPP

A3.txt

00000 01010 01010 00000

A3.hpp

ifndef A3_HPP #define A3_HPP

#include "Maze.hpp"

// implement your function distance int distance(Maze& maze, int sx, int sy, int fx, int fy) {

} // distance

#endif // A3_HPP

Objectives Practice design and implementation of recursion- (or iteration-) based algorithms Implement a component to work with larger C++ code Solve a practical problem Introduction The shortest path problem is one of the most practical and popular problems in computer science (think GPS navigation, robot routing, etc.). We are interested in the instance where a robot must find a shortest path in a maze. Maze is represented by a two-dimensional binary array (or grid) n m, where the top-left corner has coordinates (0,0) and the bottom-right corner has coordinates (n-1,m-1). 0 at position (x,y) in the array indicates open space (or passage) to which our robot can move freely. 1 indicates a wall that blocks the robot, that is, the robot cannot move to a position occupied by a wall. The array below is an example of a 4 5 maze 01010 01010 The robot starts at the position (sx,sy) and must find a shortest path to the position (fx,fy). In a single step the robot can move in one of four directions (up, down, left or right) but only to a position that is open. The shortest path is a path that requires the least number of moves from the robot to reach (fx,fy) starting at (sx,sy) For instance, if we consider our example maze, and (sx-0,sy-0) and (fx-3,fy-2), then there are two possible shortest paths of length 5, i.e. the robot must make 5 moves to reach the finishing position (3,2) from the starting position (0,0). Your task is to implement a function that will find the length of a shortest path of our robot for a given maze, starting position (sx,sy) and finishing position (fx,fy). You can assume that such path always exists. To implement the function consider the following observation. After making a move from (sx,sy) to a new position, the length of the best path the robot can take to (fx,fy), which potentially can be the shortest, is equal 1 the length of a shortest path from the new position to (fx,fy) Hints Read about BFS and DFS. If you plan on implementing this using DFS, read about dynamic program ming