本次美国代写是C++迷宫报告相关的一个Assignment

Figure 1: A maze (walls and corridors in black and white, respectively) with the path (blue) between the

entrance(green)andexit(red)ofthemaze.

Introduction

Forourthesecondpartofprojectfourwe’llimplementaclasscapableofsolvingmazes.TheDequeADTwill

beusedwithbreadth-firstsearchtofindtheshortestpathbetweenanytwopointsinthemaze(shouldsuch

apathexist).

1 The Maze Class

Theoutlineoftheclassisdefinedinthestartercodeinsidethefile Maze.hpp. Youarenotallowedtomodify

thepublicportionoftheheaderfileandthesolvedmazesmustadheretothespecificationbelow.Youwillneed

todefinethemethodsandimplementallmethodsinthe Maze.cpp file.Youshouldaddappropriatecomment

blockstoeachmethod,aswell,inMaze.cpp.Youwillneedtowritetestsinthestudent_tests.cppusingthe

Catchtestingframework,asdescribedinclass.Theincluded CMakeLists.txt filesetsupeverythingforyou.

Just generate your build directory for your development environment as described in the course work-flow

tutorial.

1.1 Mazes

Ourmazesareofsize rows-by-cols,whereeachelementeitherrepresentsacell(thatwecanmovethrough)

orawall(thatwecan’tmovethrough),withbeginningpointbeginandendpointend.Themazeitselfwillbe

storedasastd::vector<unsigned char>oflengthrows×cols,wherelinearindex0correspondstoposition

(0,0)inthemazeandlinearindex(rows×cols)-1correspondsto(rows-1, cols-1);i.e.,indexingthevector

willbedoneusingrow-majorordering(index1is(0,1),index2is(0,2),etc.).

1.2 Solving Mazes

Aninterestinguseofqueuesisinstate-spacesearchalgorithms. State-spacesearchsolvesproblemsthatcan

be formulated as a state configuration (a collection of related variables that describes the problem) where thereisaninitialstate,cleartransitionstonewstates,andameanstotestifagoalstatehasbeenreached.

Suchalgorithmscanbedescribedgenericallyusingatype state andoperationsonaprobleminstance:

• problem.initial() returnstheinitialstateoftheproblem

• problem.goal(state) returnstrueifstateisthegoalstate,elsefalse

• problem.actions(state) returnsalistofstatesresultingfrompossibletransitionsfromstate

Thealgorithmwe’llusetofindtheshortestpathbetweenthebeginning(entry)andnearestend(exit)points

inthemazeisbreadth-firstsearch:

Listing1:BFS

1 function breadth_first_search(problem) returns a solution or failure

2

3 s = problem.initial()

4 if problem.goal(s) return s

5

6 frontier is a FIFO queue with s as the initial element

7 explores is an empty set

8

9 while true

10 if frontier is empty return failure

11 s = pop next state from frontier

12 add s to explored

13 for each state s’ in problem.actions(s) do

14 if s’ not in explored or frontier then

15 if problem.goal(s’) then return s’

16 insert s’ into the frontier

Forusthe state isacellinthemazeand actions arethecellsthatwecanmoveto. Thereisnodiagonal

movement(weeithermoveup,down,left,orright)andtheorderpossibleactionsaretobeevaluatedismove

right(towardstheleftcolumn),left(towardstheleftcolumn),down(towardsthelastrow),orup(towards

thefirstrow).

Acoupleofthingstonote:

1. Notonlydowewantsolvethemazebutweneedtonotethepathwetookfromtheentrypointofthe

mazetoitsexit.Apaththroughthemazewillbedenotedby ‘*’ ineachcell.

2. You code needs to deal with mazes containing cycles (so-called braid mazes) and multiple exits. You

mustfindthenearestexistfromthestartingpoint.

3. Thefrontiermustuseyourdequeimplementation.Theexploredandfrontierinclusiontestscanbedone

usinganothercontainerinourproblem,asthereisnoinclusiontestinthedeque.

1.3 Showing Mazes

We’llusethefollowingASCIIsymbolsinourclass:

• acellis ‘ ’

• awallis ‘#’

• theentrypointofthemazeis ‘B’

• theexitpointofthemazeis ‘E’

• acellthatispartofthepathfromentrytoexitis ‘*’

Avalidmazethathasn’tbeensolvedthuslookslike:

Listing2:ASCIIrepresentationofanunsolvedmaze

1 B # E#

2 ## ##### #

3 # # #

4 ### # ###

5 # #

6 ####### #

7 #

8 ######## #

9 #

10 ########## Anditssolution:

Listing3:ASCIIrepresentationofasolvedmaze

1 B**# E#

2 ##*#####*#

3 #***#***#

4 ###*#*###

5 *****#***#

6 *#######*#

7 *********#

8 ######## #

9 #

10 ##########

Toaidindebuggingwe’veoverloadedthe operator« sothatyoucanprintmazesusing std::cout;i.e.,for

themaze m youcanuse std::cout « m.

WhileASCIIrepresentationsofmazesmaybegoodenoughfordebugging,theydon’tlookthatimpressive

tonon-coders. Thereforewe’llconvertour unsigned char representationtoimages. We’llusethefollowing

colorstorepresentASCIIsymbols:

• acellisawhitepixel

• awallisablackpixel

• theentrypointofthemazeisagreenpixel

• theexitpointofthemazeisaredpixel

• acellthatispartofthepathfromentrytoexitisabluepixel Yourclasswillbecapableofreadingandwritingmazesfromanimage.

2 Hints

• Therowandcolumnofthelinearindex x are x/cols and x%cols,respectively.

• Anelementatrow i andcolumn j hasthelinearindex j + (i ∗ cols)

• It may just be easiest to convert to the one-dimensional vectors in the header file to two-dimensional

vectors(thoughyou’llneedtostillsupportpublicmethodsthatexpectone-dimensionalvectors).

• Asimplewaytorecoverthepathafteryouhavesolvedthemazeistonotefromwhichcellyoucame

fromwhenvisitingacell.

• We’veprovidedafewtestfilestoevaluateyourmazesolvingmethod.

3 Grader

Wewillbeusinganautomaticgradertohelpyoudetermineyourassignment’scompletenessandcorrectness.

Aportionofeachassignmentgradewillbedeterminedbythenumberofpassingtestsasdeterminedbythe

autograder,withourevaluationfillingintherest.Thismeansyouknowbeforeyouturninyoursubmissionthat

alliswell.Youcansubmittotheautograderasmanytimesasyoulike,butitisratelimited(fivesubmissions

everyhour)tokeepyoufromusingitasyourcompiler.Seethiscanvasforasummaryofhowtousethegrader

(NoteisisnotWebCAT,whichmanyofyoumaybefamiliarwith).

For this assignment you should upload a zip file containing only the files: Maze.hpp, Maze.cpp, and

student_tests.cpp.Thereisabuildtargetcalled“submission”configuredbydefaulttocreatethisfilewith

thecorrectcontentsinyourbuilddirectory.

4 Submission

Onceyouaresatisfiedwithyourcode,uploadazipfilecontaining(only)Maze.hpp,Maze.cpp,andstudent_tests.cpp

throughCanvasattheassignmentlink. Youshouldnotsubmittheotherfilesfromthestartercode,noryour

build directory. There is a build target called “submission” configured by default to create this file with the

correctcontentsinyourbuilddirectory.

5 Grading

Thereare60pointsallocatedtothisassignment.

• Correctlysubmittingtherequiredfiles:2points

• Yourtestscompile:3points

• Yourtestspass:10points(proportional)

• Instructortestscompilewithyourcode:3points

• Instructortestspass:30points(proportional)

• Designrequirementsmet(e.g.,codeandtestquality,comments):12points

Asperthesyllabus,goodfaitheffortsmustbemadetowritecomprehensivetests.Sincethereisnowayto

testforthisatcompileorruntime(atthispoint),shouldthegrader(person)deemyourteststobewoefully

lackingyouwilllosenotonlydesignpointsbutalsothepointsgivenbytheautograder. Eachmethodshould

betested.