辅导EECS 281程序、写作C++语言程序

” 辅导EECS 281程序、写作C++语言程序EECS 281 Winter 2021Project 1:Rescue the CountessDue Tuesday, February 9, 11:59 PMOverviewIts a-me, Marco! Marco of the Fungus Province has just received news that Louser has takenCountess Cherry captive in his dark, maze-like castle. With his twin brother, Luigino, Marco hastraveled many miles to reach the castle, dodging flying shells and jumping on angrymushrooms. Now that he has entered the castle, he needs your help to rescue the Countess.Using C++, you Must implement some basic path finding algorithms to guide Marco to theCountess and foil Lousers evil plans!Castle LayoutYou must help Marco navigate through Lousers castle. The castle contains up to 10 rooms,with warp pipes to travel between them. The rooms are all squares of the same size (NxN).Your program will be given a map or description of the castle that uses the following symbols:● . walkable room space● # walls (which cannot be walked on or through)● ! one of Lousers minions (which cannot be walked on or through)● A digit 0 to 9 which indicates a warp pipe traveling to the same spot in the roomwith the corresponding number● S Marcos starting location● C location of Countess CherryYou can assume, for the files that we give you, that there is exactly one location for CountessCherry and exactly one starting point for Marco. You still might want to verify this, just in casean input file that you create breaks this rule.Because you have a copy of the castle map, your task is to plan a path for Marco from thestarting position (S) to the Countess (C) that does not pass through any walls (#) orminions (!). Marco can walk next to the minions, but cannot walk on top of them. Marcodoesnt have time to get in a fight today!Rooms are to be treated as if they are surrounded by walls; you are to treat both walls and roomedges as impassable terrain.Marco can discover new locations north, east, south or west from any room space (.) as wellVersion 1-20-21 2021 Regents of the University of Michigan1as the starting location; no discoveries may be made diagonally. Your path planningprogram must check that it does not move Marco off of the map, onto walls (#), or ontominions (!).In addition, when Marco steps onto a warp pipe (digits 0-9), he will only be able to discover thelocation in the same row and column of the room corresponding to the warp pipes number. IfMarco steps on a warp pipe with digit, d, at row and column (r, c), in any room, then hell beable to discover (r, c) in the room d. It is possible for this to continue from warp pipe to warppipe, if there are multiple rooms with warp pipes in the same location.If room d doesnt exist, no new location can be discovered. Youll need to check for this. Forexample, a castle with 2 rooms might have a pipe labelled 5, but room 5 does not exist, soMarco wont use this pipe.Input file format (The Castle Map)The program gets its description of the castle from a file that will be read from standard input(cin). This input file is a simple text file specifying the layout of the castle. We require that youmake your program compatible with two input modes: map (M) and coordinate list (L).The reason for having two input modes is that a large percentage of the runtime of yourprogram will be spent on reading input or writing output. Coordinate list mode exists so that wecan express very large maps with a minimal amount of input data; map input mode exists toexpress maps whose input files are also easily human readable.For both input modes (M and L):● The first line of every input file will be a single character specifying the input mode, M orL (without quote marks). Unlike the output mode, which is given on the commandline (see below), this is part of the input file.● The second line will be a single integer 1 R 10 indicating the number of rooms.● The third line will be a Single integer 1 N, indicating the size of each (and every) roomof the castle (each room is NxN in size and all rooms are the same size).You can assume that N (and thus a row or a column index) will fit inside of an unsigned integervariable (unsigned int or uint32_t),.Comment lines begin with // and they are allowed anywhere in the file after the first threelines. When developing your test files, it is good practice to place a comment on line 4describing the nature of the Castle in the test file. Any castles with noteworthy characteristics fortesting purposes should be commented. The map file is also easier to read if there is acomment line identifying the room number before the description of that room, but this is notrequired. Comments are Allowed in either input mode.Version 1-20-21 2021 Regents of the University of Michigan2Additionally, there may be extra blank/empty lines at the end of any input file, your programshould ignore them. If you see a blank line in the file, you may assume that you have hit theend.Map input mode (M):For this input mode, the file Should contain a map of each room, in order. The rooms arespecified beginning with the lowest number room and working up. The lowest room is room 0;that is to say, the rooms are 0-indexed.An example map mode input file for a castle with two 4×4 rooms:M24//sample M mode input file with two 4×4 rooms//castle room 0.C………S#.1#//castle room 1….#….!..#…BEWARE: DO NOT copy/paste from a PDF file! PDF files contain ligatures (invisiblecharacters) that may cause your code (or the autograder) to behave in unexpected ways.Copy from the sample files that we give you, or retype it by hand.Coordinate list input mode (L):A coordinate list input file Will contain a list of coordinates for at least all walls, minions, andwarp pipes in the rooms. Only one coordinate should appear on a given line. We do not requirethat the coordinates appear in any particular order. A coordinate is specified in precisely thefollowing form: (room,Row,col,character). The row and col positions range from 0 toN-1, where N is the value specified at the top of the file. By default, all unspecified coordinateswithin the rooms are of type . (room space); however, it is still valid to redundantly specifythem.Here is a valid L mode input file that describes rooms that are identical to those that the sampleM input file did:Version 1-20-21 2021 Regents of the University of Michigan3L24//sample L mode input file, two 4×4 rooms//castle room 0(0,0,1,C)(0,1,0,.)(0,2,3,S)(0,3,0,#)(0,3,2,1)(0,3,3,#)//castle room 1(1,1,0,#)(1,2,1,!)(1,3,0,#)(1,3,3,.)Invalid coordinates (for a castle with two 4×4 rooms):(2,1,2,#) — Room 2 does not exist!(1,4,2,.) — Row 4 does not exist!(0,1,5,!) — Col 5 does not exist!(0,0,1,F) — F is an invalid map character!Routing schemesYou are to develop two routing schemes to help Marco get from the starting location to thelocation of Countess Cherry:● A queue-based routing scheme● A stack-based routing schemeBe sure to read the document on Canvas titled Project 1 the STL and You; it has someexcellent tips, Plus a way to implement the two different routing schemes with a single searchcontainer (the deque).In the routing scheme use a search container (queue or stack) of locations within the castle.First, initialize the algorithm by adding the start position S to the search container. Then, loopthrough the following steps:1. Remove the next position from the search container.2. If that position has a warp pipe, Add the corresponding position that the pipe leads to,i.e., the same row/col position but with the specified room number. As noted below, onlyadd this position if it has not been added to the search container before.Version 1-20-21 2021 Regents of the University of Michigan43. If the position is not a warp pipe, then add all locations adjacent to the location you justremoved that are available to move into (walkable room space, warp pipes, or theCountesss location). Add any locations that you are allowed to move to from yourpresent location in the following order: north, east, south, and west.4. As you add any of these spaces (step 2 or 3) to the search container, check to see if anyof them is the location of the Countess C; if so, stop searching for a path.If the search container becomes empty before you reach the Countess C, the search hasfailed and there is no Path to rescue the Countess.Whenever you add a position to the search container, you have discovered it. Do notdiscover any position more than once. Remember that from a walkable room space tile .or your starting location S you can only discover locations north, east, south, or west. Warppipes are the only way of moving between rooms.When visiting a warp pipe, you still have to check that you havent added its targetlocation to the data structure when you see it. This will help you prevent Marco fromfollowing warp pipe loops. Also, make sure that Marco doesnt warp onto an enemy or into asolid wall! This is considered unhealthy.The program must run to completion within 35 seconds of total CPU time (user + system)- programs running for longer than this period will receive 0 points on that test case. Inmost cases 35 seconds is much more time than you should need; even if you finish before 35seconds, you may still receive no points because your solution is too slow. See the timemanpage for more information (this can be done by entering man time to the command line).We may test your program on very large maps (up to several million locations). Be sure you areable to navigate to the Countess in large castle maps within 35 seconds. Smaller castle mapsshould run MUCH faster.Libraries and RestrictionsUnless otherwise stated, you are allowed and encouraged to use all parts of the C++ STL andthe other standard header files for this project. You are not allowed to use other libraries (eg:boost, pthread, etc). You are not Allowed to use the shared_pointer or unique_pointerconstructs from the memory include file (we want you to learn proper use of pointers yourself).You are not allowed to use the C++11 regular expressions library (it is not fully implemented ingcc 6.x) or the thread/atomics libraries (it spoils runtime measurements).Output file formatThe program will write its output to standard output (cout). Similar to input, we require that youimplement two possible output formats. Unlike input, however, the output format will bespecified through a command line option –output, or -o, which will be followed by anargument of M or L (M for map output and L for coordinate list output). See the section onVersion 1-20-21 2021 Regents of the University of Michigan5command line arguments below for more details.For both output formats, you will show the path you took from start to finish.If there is no valid solution, then, regardless of output mode, outputNo solution, N tiles discovered.(where N is the number of tiles discovered) followed by a newline.Map Output Mode (M):For this output mode, you should first print the starting location (see the example below). Thenprint the map of the castle rooms, replacing existing characters as needed to show the path youchose. Beginning at the starting location, overwrite the characters in the path with n, e,s, w, or p to indicate which tile Marco moved to next. All pipes Marco used in the finalpath should be overwritten by p, regardless of what room they lead to or from. Do notoverwrite the location of the Countess C at the end of the path, but do overwrite the S atthe beginning. For all spaces that are not a part of the path, simply reprint the original roommap space. You Should only create comments to indicate the room numbers and format themas shown below, all other comments from the input files should be omitted.Thus, for the sample input file specified earlier, using the queue-based routing scheme and map(M) style output, you should produce the following output:Start in room 0, row 2, column 3//castle room 0.Cww…n…n#.1#//castle room 1….#….!..#…Using the same input file but with the stack-based routing scheme, you should produce thefollowing output:Start in room 0, row 2, column 3//castle room 0eC..n…nwwwVersion 1-20-21 2021 Regents of the University of Michigan6#.1#//castle room 1….#….!..#…We have highlighted the modifications to the output in red to call attention to them; do notattempt to color your output (this isnt possible, as your output must be a plain text file).Coordinate List Output Mode (L):For this output mode, you should print only the coordinates that make up the path you traveled.You should print them in order, from (and including) the starting position to the C (but youshould not print the coordinate for C). The coordinates should be printed in the same format asthey are specified in coordinate list input mode (room,row,col,character). Thecharacter of the coordinate should be n, e, s, w or a p to indicate spatially whichtile is moved to next (as with map output, the p indicates that a warp pipe was taken). Youshould discard all Comments from the input file, but you should add one line, just before you listthe coordinates of the path that says Path taken:.The following are examples of correct output format in (L) coordinate list mode that reflect thesame solution as the Map output format above:For the queue solution:Path taken:(0,2,3,n)(0,1,3,n)(0,0,3,w)(0,0,2,w)For the stack solution:Path taken:(0,2,3,w)(0,2,2,w)(0,2,1,w)(0,2,0,n)(0,1,0,n)(0,0,0,e)There is only one acceptable solution per routing scheme for each castle. If no valid routeexists, the program should print No solution, N tiles discovered. (followed by anewline), where N is the number of tiles you discovered while searching, and no other output, inVersion 1-20-21 2021 Regents of the University of Michigan7either output mode. If this occurs, do not output the starting location or Path taken: line.Be aware that input and output modes are independent of each other. Each test can use eitherinput mode and either output mode. They may or may not be the same.Command line argumentsYour program should take the following case-sensitive command line options (when we say aswitch is set, it Means that it appears on the command line when you call the program):● –stack, -s: If this switch is set, use the stack-based routing scheme.● –queue, -q: If this switch is set, use the queue-based routing scheme.● –output (M|L), -o (M|L): Indicates the output file format by following the flagwith an M (map format) or L (coordinate list format). If the –output option is notspecified, default to map output format (M), if –output is specified on the commandline, the argument (either M or L) to it is required. See the examples below regardinguse.● –help, -h: If this switch is set, the program should print a brief help message whichdescribes what the program does and what each of the flags are. The program shouldthen exit(0) or return 0 from main().When we say –stack, or -s, we mean that calling the program with –stack does the samething as calling the program with -s. See getopt for how to do this.Legal command line arguments must include exactly one of –stack or –queue (or theirrespective short forms -s or -q). If none are specified or more than one is specified, theprogram should print an informative message to standard error (cerr) and call exit(1).Examples of legal command lines:● ./superMarco –stack infile outfile○ This will run the program using the stack algorithm and map output mode.● ./superMarco –queue –output M infile outfile○ This will run the program using the queue algorithm and map output mode.● ./superMarco –stack –output L infile outfile○ This will run the program using the stack algorithm and coordinate list outputmode.Notice that we are using input and output redirection here. While we are reading ourinput from a file and sending our output to another file in this case, we are NOT using filestreams! The command redirects the file specified by the next command line argument to bethe standard input (cin) for the program. The command redirects the output of the program(things sent to cout) to be printed to the file specified by the next command line argument. Theoperating system makes calls to Cin to read the input file and it makes calls to cout to write toVersion 1-20-21 2021 Regents of the University of Michigan8the output file. Come to office hours if this is confusing!Examples of illegal command lines:● ./superMarco –queue -s infile outfile○ Contradictory choice of routing● ./superMarco infile outfile○ You must specify either stack or queueTesting your solutionIt is extremely frustrating to turn in code that you are certain is functional and then receivehalf credit. We will be grading for correctness primarily by running your program on a number oftest cases. If you have a single silly bug that causes most of the test cases to fail, you will get avery low score on that part of the project even though you completed 95% of the work. Most ofyour grade will come from correctness testing. Therefore, it is imperative that you test yourcode thoroughly. To help you do this we will require that you write and submit a suite of testfiles that thoroughly test your project.Your test files will be used to test a set of buggy solutions to the project. Part of your grade willbe based on how many of the bugs are exposed by your test files. (We say a bug is exposed bya test file if the test file causes the buggy solution to produce different output from a correctsolution.)Each test file should be an input file that describes a castle in either map (M) or coordinate list(L) format. Each test file should be named test-n-flags.txt where 1 n 15. The flagsportion should include a combination of letters of flags to enable. Valid letters in the flagsportion of the filename are:● s: Run stack mode● q: Run queue mode● m: Produce map mode output● l: Produce list Mode outputThe flags that you specify as part of your test filename should allow us to produce a validcommand line. For instance, dont include both s and q, but include one of them; include m or l,but if you leave it off, well run in map output mode. For example, a valid test file might benamed test-1-sl.txt (stack mode, list output). Given this test file name, we would run yourprogram with a command line similar to the following (the autograder will use a randomcombination of long and short options, such as –output instead of -o):./superMarco -s –output L test-1-sl.txt test-1-output.txtTest files may have no more than 10 levels, and the size of a level may not exceed 8×8. YouVersion 1-20-21 2021 Regents of the University of Michigan9may submit up to 15 test files (though it is possible to get full credit with fewer test files). Thetest cases the autograder runs on your solution are NOT limited to 10x8x8; your solution shouldnot impose any size limits (as long as sufficient system memory is available).Errors you must check forA small portion of your grade will be based on error checking. You must check for the followingerrors:● Input errors: illegal map characters (you should check in both M and L input modes).● For L input mode, you must check that the room, row, and column numbers of eachcoordinate are all valid positions.● More or less than one –stack or –queue or -s or -q on the command line. Youmay assume the command line will otherwise be correct (this also means that we will notgive you characters other than M or L to –output).In all of these cases, print an informative error message to standard error (cerr) and callexit(1). In the starter files, look at the file named Error_messages.txt. If you output anyone of those standard error messages when the input is actually valid, the autograder will repeatthe error message Back to you. This can be helpful when your program thinks that a valid inputis invalid, because you can more easily figure out what went wrong.You do not need to check for any other errors.Assumptions you may make● You may assume we will not put extra characters after the end of a line of the map orafter a coordinate.● You may assume that coordinates in coordinate list input mode will be in the format(room,row,col,character).● You may assume that there will be exactly one start location S and exactly onelocation of the Countess C in the map.● You may assume that we will not give you the same coordinate twice for the coordinatelist input mode.● You may assume the input mode line and the integer dimensions of the castle on linestwo and three at the beginning of the input file will be by themselves, withoutinterspersed comments, and that they will be correct.Submission to the AutograderDo all of your work (with all needed files, as well as test files) in some directory other than yourhome directory. This will be your submit directory. Before you turn in your code, be sure that:Version 1-20-21 2021 Regents of the University of Michigan10● Every source code and header file contains the following project identifier in a commentat the top of the file:● // Project Identifier: B99292359FFD910ED13A7E6C7F9705B8742F0D79● The Makefile must also have this identifier (in the first TODO block).● DO NOT copy the above identifier from the PDF! It might contain hidden characters.Copy it from the Identifier.txt file from Canvas instead.● You have deleted all .o files and your executable(s). Typing make clean shallaccomplish this.● Your makefile is called Makefile. Typing make -R -r builds your code without errorsand generates an executable file called superMarco. The command line options -Rand -r disable automatic build rules, which will not work on the autograder.● Your Makefile specifies that you are compiling with the gcc optimization option -O3. Thisis extremely important for getting all of the performance points, as -O3 can often speedup code by an order of Magnitude. You should also ensure that you are not submitting aMakefile to the autograder that compiles with the debug flag, -g, as this will slow yourcode down considerably. If your code works when you dont compile with -O3 andbreaks when you do, it means you have a bug in your code!● Your test files are named test-n-flags.txt and no other project file names begin with test.Up to 15 test files may be submitted.● The total size of your program and test files does not exceed 2MB.● You dont have any unnecessary files or other junk in your submit directory and yoursubmit directory has no subdirectories.● Your code compiles and runs correctly using the g++ compiler. This is available on theCAEN Linux systems (that you can access via login.engin.umich.edu). Even ifeverything seems to work on another operating system or with different versions of GCC,the course staff will not support anything other than GCC running on CAEN Linux. At themoment, the default version installed on CAEN is 4.8.5, however we want you to useversion 6.2.0 (available on CAEN with a command and/or Makefile); this version is alsoinstalled on the autograder machines.Turn in all of the following files:● All your .h, .hpp, and .cpp files for the project● Your Makefile● Your test filesYou must prepare a compressed tar archive (.tar.gz file) of all of your files to submit to theautograder. One way to do this is to have all of your files for submission (and nothing else) inone directory. Our Makefile provides the command make fullsubmit. Alternately you cango into this directory and run this command:dos2unix *; tar czf ./submit.tar.gz *.cpp *.h *.hpp Makefile test*.txtThis will prepare a suitable file in your working directory.Version 1-20-21 2021 Regents of the University of Michigan11Submit your project files directly to either of the two autograders at: httpss://g281-1.eecs.umich.edu/ or httpss://g281-2.eecs.umich.edu/. When the autograders areturned on and accepting submissions, there will be an announcement on Piazza. Theautograders are identical and your daily submission limit will be shared (and kept track of)between them. You may submit up to three times per calendar day (more during the Spring).For this purpose, days begin and end at midnight (Ann Arbor local time). We will count onlyyour best submission for your grade. If you would instead like us to use your LASTsubmission, see the autograder FAQ page, or use this form. If you use an online revisioncontrol system, make sure that your projects and files are PRIVATE; many sites makethem public by default! If someone searches and finds your code and uses it, this couldtrigger Honor Code Proceedings for you.Please make sure that you read all messages shown at the top section of yourautograder results! These messages will help explain some of the issues you are having(such as losing points for having a bad Makefile or using disallowed libraries).Grading80 points — Your grade will be primarily based on the correctness of your algorithms. Yourprogram must have correct and working stack and queue algorithms and support both types ofinput and output modes. Additionally: Part of your grade will be derived from the runtimeperformance of your algorithms. Fast running algorithms will receive all possible performancepoints. Slower running algorithms may receive only a portion of the performance points. Theautograder machines keep track of the fastest run times (click on View scoreboard from theautograder project page). You may track your progress relative to other students andinstructors there.10 points — No memory leaks. Solutions that are proven to run (passing certain autograder testcases) will also be run through valgrind, to check for memory leaks at exit. This is somethingyou should do yourself, to check for memory leaks as well as a number of other issues thatvalgrind can enumerate. Valgrind is available at the CAEN command prompt, and can also bedownloaded to run on Linux-based personal environments.10 points — Testing and Bug Finding (effectiveness at exposing buggy solutions withuser-created test files).Grading will be done by the autograder.Version 1-20-21 2021 Regents of the University of Michigan12Empirical efficiencyWe will check for empirical efficiency both by measuring the memory usage and running time ofyour code and by reading the code. We will focus on things such as whether you useunnecessary temporary variables, whether you copy data when a simple reference to it will do,and whether you use an O(n) algorithm or an O(n2) algorithm.Coding styleAlthough your project will not be graded on style, style is a very important part of programmingand software development. Among other things, good coding style consists of the following:● Clean organization and consistency throughout your overall program● Proper partitioning of code into header and cpp files● Descriptive variable names and proper use of C++ idioms● Effective use of library (STL) code● Omitting globals, unnecessary literals, or unused libraries● Effective use of comments● Reasonable formatting – e.g. an 80 column display● Code reuse/no excessive copy-pasted code blocks● Effective use of comments includes stating preconditions, invariants, and postconditions,explaining non-obvious code, and stating big-Oh complexity where appropriateIt is extremely helpful to compile your code with the gcc options: -Wall -Wextra-pedantic -Wconversion. This will help you catch bugs in your code early by having thecompiler point out when you write code that is either of poor style or might result in behavior thatyou did not intend.Hints and advice● Design your data structures and work through algorithms on paper first. Draw pictures.Consider”