StartSearch.java
This class will have the followingprivateinstance variable
oMap targetMap;
oThis variable will reference the object representing the map where Cupid and the
targets are located. This variable must be initialized in the constructor for the
class, as described below.
oint numArrows, for how many arrows Cupid has fired so far. Compare this to the
quiverSize from the Map.
oint inertia, which is used for tracking how many times an arrow has travelled in
the same direction. It should start at 0 and increase everytime an arrow moves in
the same direction.
oint direction, which is used for tracking the direction of the arrow. 0 is north, 1 is
east, 2 is south, 3 is west. (Or Up, Right, Down, Left, respectively)
It should import: import java.io.FileNotFoundException; & import java.io.IOException; You must implement the following methods in this class:
•StartSearch(String filename)
oThis is the constructor for the class. It receives as input the name of the file
containing the description of the map. In this method you must create an object of the class Map (described in the provided files) passing as parameter the given input file; this will display the map on the screen.
oRead them if you want to know the format of the input files.•static void main(String[] args).
oThis method will first create an object of the classStartSearchusing the constuctorStartSearch(args[0]).
oArgs[0]will be the name of a map file,args[1]will be the number of cells that the arrow can travel before it falls to the ground.
oIf and only if a size argument is provided, your algorithm should count how many targets can be found in a path that is at mostargs[1]long with the number of arrows determined by the map.
oWhen you run the program, you will pass as command line arguments the name of the input file (see following section after Java classes), and the number of cells that Cupid can hit from his starting point to find target along with the number of arrows.
oYour main method then will try to find a path from Cupid to the targets according to the restrictions specified above.
oThe algorithm that looks for a path from the initial cell to the destinations must use a stack and it cannot be recursive.
oSuggestions on how to look for this path are given in the next section. The code provided to you will show the path selected by the algorithm as it tries to reach the target cells, so you can visually verify if your program works.
oThe main method should exit by printing out the number of targets found given the restrictions above (maximum arrow length, maximum number of arrows,Cupid won’t shoot down the same pathtwice.
•MapCell nextCell(MapCell cell).
oTheparameteristhecurrentcell.
oThis method returns the best cell to continue the path from the current one, as
specified early in the limitations.
oRefertothoseprioritieswhencodingthissection.
If several unmarked cells are adjacent to the current one and can be selected as part of the path (rememberthe arrow will stay on the same path first), then this method must return one of them in the following order:
▪ A target cell
▪ A cross path cell.
▪ If there are several possible cross path cells, then the one with the
smallest index is returned.
▪ A vertical path cell or a horizontal path cell with smallest index
▪ Read the description of the class MapCell below to learn how to get the
index of a neighbouring cell.
▪ If there are no unmarked cells adjacent to the current one that can be
used to continue the path, this method returns null.
oYour program must catch any exceptions that are thrown by the provided code.oFor each exception caught, an appropriate message must be printed.
oThe message must explain what caused the exception to be thrown.
You can write more methods in this class but they must be declared as private.
Algorithm for Computing a Path
Below is a description for an algorithm that will look for a path for Cupid to the targets. It will be helpful to understand the algorithm deeply before attempting to implement it. There are better algorithms for finding targets given a maximum path length, but they may not pass all the tests. Implement the algorithm as described to make sure your code passes the test cases.
You must use a stack to keep track of which cells are in the path, and it cannot be recursive. Writing your algorithm in pseudocode will make coding it in Java easier and is helpful to show to the TAs and the instructors if you need help.
▪ Initialize the number of found targets to 0.
▪ Create a stack based on the command line inputs
▪ Get the start cell (Cupid) using the methods of the supplied class Map.
▪ Push the starting cell into the stack and mark the cell as inStack.
▪ You will use methods of the class MapCell to mark a cell.
▪ While the stack is not empty and Cupid has arrows left, and the arrow path length has
not been reached, perform the following steps:
oPeek at the top of the stack to get the current cell.
oFind the next unmarked neighbouring cell (use method nextCell from class
StartSearch to do this).oIf one exists:
▪Push the neighbouring cell into the stack and mark it as inStack.▪(If max path length given) Increase the path length counter
▪If the best neighbouring cell is a target, increase the number of targets hitoOtherwise, since there are no unmarked neighbouring cells that can be added to the path, pop the top cell (and increase the path length counter) from the stack.
▪While the stack is not empty perform the following:
oPop the top cell from the stack.
oWhen popping cells adjacent to Cupid, mark as out of stack.
Your program must print a message indicating how many targets were hit
Note that your algorithm does not need to find the shortest path from Cupid to all the targets, or even the shortest path with the pathing restraints.
Command Line Arguments
Your program must read the name of the input map file from the command line. You can run the program with the following command:
java StartSearch nameOfMapFile (optional)maxPathLength
Where nameOfMapFile is the name of the file containing the map, and maxPathLength is the longest path that Cupid’s arrowcan take to find targets.
You can use the following code to verify that the program was invoked with the correct number of arguments:
public class StartSearch {
public static void main (String[] args) {
if (args.length
System.out.println("You must provide the name of the input file"); System.exit(0);
}
String mapFileName = args[0];
int maxPathLength = Integer.parseInt(args[1]); ...