墨尔本大学COMP10002Assignment2课业解析题意：
C语言实现网格路径规划，任务包括可视化网格路径，检测路径合法性，支持修复非法路径
解析：
第一阶段要求完成读取地图和分析数据功能。上面的地图输入格式如下：第一行代表地图行列，第二行和第三行分别表示出发点和终点，第四行至$表示障碍，$标志地图信息加载完毕，$至最后一行表示路径信息。 该阶段要打印如下内容：其中最后一行依据路径状态打印5条语句之一。
若路径起始点和地图出发点不同，打印Initial cell in the route is wrong!
若路径终点和地图终点不同，打印Goal cell in the route is wrong!
若每次移动超过两格，打印There is an illegal move in this route!
若路径上有障碍，打印There is a block on this route!
其它情况下打印The route is valid!
第二阶段要求把地图和路径可视化（使用ASCII码），以及遇到障碍重新寻路。
Image
第三阶段展示路径修复的全过程。 代码示例： 涉及知识点： 数组、链表、队列更多可加微信讨论微信号ITCSdaixeipdf
School of Computing and Information Systemscomp10002 Foundations of AlgorithmsSemester 2, 2019Assignment 2Learning OutcomesIn this project, you will demonstrate your understanding of dynamic memory and linked data structures (Chapter10), and extend your skills in terms of program design, testing, and debugging. You will also learn aboutroute planning, and implement a simple route re-planning mechanism in preparation for the more principledapproaches that are introduced in comp20007 Design of Algorithms.Grid-Based Route (Re-)PlanningRoute planning is used in the navigation of autonomous agents, e.g., self-driving vehicles, robots, and humans(think of mapping services). Grid-based route planning studies the problem of constructing a route from an initialcell to a destination cell in a two-dimensional space subdivided into grid cells that are either blocked or empty.Figure 1a shows an example grid of 10 rows and 10 columns, the initial cell at row 0 and column 0 denoted by I(yes, we count from zero) and the destination (goal) cell at row 9 and column 9 denoted by G. The green arrowsshow the planned moves to get from I to G that omit the blocks shown as orange squares.01234567890 1 2 3 4 5 6 7 8 9IG(a)01234567890 1 2 3 4 5 6 7 8 9IG(b)01234567890 1 2 3 4 5 6 7 8 9IG(c)01234567890 1 2 3 4 5 6 7 8 9IG(d)01234567890 1 2 3 4 5 6 7 8 9IG(e)01234567890 1 2 3 4 5 6 7 8 96 5 4 5 6I6 5 4 3 4 5 66 5 4 3 2 3 4 5 65 4 3 2 1 2 3 4 5 64 3 2 1 0 1 2 3 4 55 4 3 3 4 56 5 4 5 6 5 4 56 5 6 56G(f)Figure 1: Grids with blocks and routes.As the environment changes, i.e., blocks get removed or placed at some new cells, the planned route may becomeinvalid. Figure 1b shows the grid from Figure 1a with a new configuration of blocks. The original route fromFigure 1a is invalid in Figure 1b, as it visits blocked cells, see the red arrows in the figure. If an agent, e.g.,a robot, takes the planned route from Figure 1a to get from cell I to cell G in the grid in Figure 1b, it will getblocked. However, at that point, it can request the new locations of all blocks from the external sensors andre-plan to move around the obstacles and get back on the original route, as shown in Figure 1c. Figure 1d showsa subsequent configuration of blocks that breaks the re-planned route from Figure 1c in two places. An agentthat attempts to follow that route will get blocked for the first time at the cell at row 4 and column 2. Using theavailable data from the sensors, it may then decide to re-plan the route to take the green arrows in Figure 1e. Notethat the agent may need to revisit some cells. The red path in Figure 1e is now useless and should be forgotten.1Input DataYour program should read input from stdin. The first line of the input encodes the dimensions of the grid, forexample 10×20 specifies that the grid has 10 rows and 20 columns. The second line of the input encodes theinitial cell of the agent in the grid, while the third line encodes the goal cell. A cell is encoded using the format[r,c], where r and c are numbers that stand for, respectively, the row and column of the cell. Subsequent inputlines specify positions of blocks in the grid, one block cell per line. An input line with a single character $denotes the end of block lines. The input lines that follow encode a route of the agent in the grid. A route isencoded by alternating cells and ->, for example [0,0]->[0,1]->[0,2] encodes the route that starts at cell[0,0], and then proceeds via cell [0,1] to cell [0,2]; no blanks or tabs are used in encodings of routes, whilea single newline character may follow ->. For example, the following file test0.txt encodes the grid and routefrom Figure 1a (the numbers in italics show line numbers and are not part of the input file).1 10×102 [0,0]3 [9,9]4 [1,0]5 [1,1]6 [1,2]7 [1,3]8 [8,9]9 [8,8]10 [8,7]11 [8,6]12 [8,5]13 $14 [0,0]->[0,1]->15 [0,2]->[0,3]->16 [0,4]->[1,4]->17 [2,4]->[3,4]->18 [4,4]->[5,4]->19 [6,4]->[7,4]->20 [8,4]->[9,4]->21 [9,5]->[9,6]->22 [9,7]->[9,8]->23 [9,9]24Stage 0 – Reading and Analyzing Input Data (8/15 marks)The first version of your program should read the input from stdin and print out some basic information sothat you can be sure you have read the inputs correctly. Your program should also ensure that the supplied routeis valid, i.e., it starts in the initial cell, ends in the goal cell, consists of legal moves (one cell moves and nodiagonal moves) and does not visit a cell with a block. The required output from this stage is the followingsummary (generated for the test0.txt example input file shown above):mac: ass2-soln < test0.txt==STAGE 0=======================================The grid has 10 rows and 10 columns.The grid has 9 block(s).The initial cell in the grid is [0,0].The goal cell in the grid is [9,9].The proposed route in the grid is:[0,0]->[0,1]->[0,2]->[0,3]->[0,4]->[1,4]->[2,4]->[3,4]->[4,4]->[5,4]->[6,4]->[7,4]->[8,4]->[9,4]->[9,5]->[9,6]->[9,7]->[9,8]->[9,9].The route is valid!The last line in the above summary reports the status of the route that can take one of these five values:Status 1: Initial cell in the route is wrong!Status 2: Goal cell in the route is wrong!Status 3: There is an illegal move in this route!Status 4: There is a block on this route!Status 5: The route is valid!Status 1 is printed if the first cell in the route is different from the initial cell supplied at line 2 of the input.Status 2 is printed if the last cell in the route is different from the goal cell given at line 3 of the input. Status 3is printed if the route contains a move that traverses more than one cell. Status 4 reports the presence of a blockat one of the cells visited in the route. Otherwise, Status 5 should be printed. The status checks should bedone in the order shown, and if a certain status holds, it should be reported and no further checks carried out.When printing a route, print no more than five cells per line separated by ->. Do not use blanks or tabs whenprinting a route. A newline character may follow ->. Refer to sample output files for further examples of printedroutes. Note that the outputs generated by your program should be exactly the same as the sample outputs forthe corresponding inputs. You should not assume the maximal allowed sizes for the input grid and route and,thus, use malloc to store the grid in a two dimensional (2D) array, and linked lists to store routes.Stage 1 – Drawing and Replanning (13/15 marks)Extend your program to visualize the input grid and route, attempt repair of a broken route, and visualize therepaired route. All of the Stage 0 output should be retained, then your Stage 1 output should start with this line:201234567890I****1####*2 *3 *4 *5 *6 *7 *8 *#####9 *****G(a)01234567890I****1 *2 *3 *4 *5 ###6 *7 *8 *9 *****G(b)01234567890I****1 *2 *3 *4 ***5 *###6 ***7 *8 *9 *****G(c)01234567890I****1 *2 *3 *4 ***5######## #6 ***7 *8 #9 #####**G(d)01234567890I****1 *2 *3 *4 *******5########*#6 *7 *8 # *9 ##### *G(e)Figure 2: Examples of grid visualizations using ASCII characters.==STAGE 1=======================================It should be followed by a visualization of the input route in the grid using ASCII characters, as shown inFigure 2; note that each of the five subfigures in Figure 2 is encoded using eleven rows, where each row haseleven characters with blanks encoded using the character with ASCII code 32. For example, Figure 2a showsthe intended ASCII encoding of the grid and route from the test0.txt input file (also shown in Figure 1a).In an ASCII visualization, the initial cell is encoded as character I, the goal cell as G, a cell with a block as#, and a visited (at least once) cell on the route as *. If a visited cell is also the initial cell, goal cell, or containsa block, then I, G, or #, respectively, should be printed, not *. If the status of the input route is not equal to 4,refer to the description of Stage 0, the output of Stage 1 terminates. Otherwise, your program should attempt torepair only the first (closest to the initial cell) broken segment of the route, and print (i) the ASCII visualizationof the repaired route in the grid and (ii) all the steps and status of the repaired route. For exampl
e, Figure 2bshows the ASCII visualization of the grid and route from the test1.txt input file (also shown in Figure 1b),while Figure 2c shows the ASCII visualization of the corresponding repaired route (also shown in Figure 1c).The visualizations of the input grid and route, the visualization of the repaired route in the grid, and the stepsand status of the repaired route should be separated by the line below.————————————————The output of the repaired walk should follow the instructions given in Stage 0. File test1-out-mac.txtcontains the exact result of the execution: “mac: ass2-soln < test1.txt > test1-out-mac.txt”.We exemplify the procedure for repairing a broken route segment using the route in Figure 1b; also shownusing ASCII visualization in Figure 2b. This route has one broken segment that starts at cell [4,4] and ends atcell [6,4]. To repair this segment, we construct a queue of pairs, where each pair is composed of coordinatesof a grid cell and a counter value. We then initialize the queue with the pair composed from the cell where thebroken segment starts and counter value of zero, the pair ([4,4],0) in the running example. Starting from thefirst pair, we then traverse the queue. When traversing a pair in the queue, for each cell in the grid that is adjacentto the cell in the traversed pair and is not blocked, we add a fresh pair to the end of the queue composed of theadjacent cell and a counter value that is greater than the counter value in the currently traversed pair by one.When visiting the adjacent cells in order to add fresh pairs to the queue, we first visit the cell above, then below,then to the left, and finally to the right from the current cell. Hence, after visiting the pair ([4,4],0), the queuecontains([4,4],0),([3,4],1),([4,3],1),([4,5],1). The traversal then continues at pair ([3,4],1).The traversal of the queue terminates once the last pair in the queue is processed or a pair that contains a cell inthe route that follows the start of the broken segment is added to the queue. In the latter case, we have discovereda repair of the broken segment!In the running example, when the traversal of the queue terminates, the queue contains pairs with all the cellsmarked with numbers in Figure 1f; the numbers indicate the counter values associated with the correspondingcells, while the last pair in the queue is ([6,4],6). Next, we construct a route fragment between cell s atwhich the broken segment starts and cell t from the last pair in the queue by walking from cell t towards cells (going backward) by progressing, at each cell, towards an adjacent cell with the smallest counter value; ifmultiple adjacent cells have the same counter value, the preference is given to the one that comes earlier inthis list: above, below, left, right of the current cell. Thus, in the running example, the fragment of the route[4,4]->[5,4]->[6,4] gets replaced with [4,4]->[4,3]->[4,2]->[5,2]->[6,2]->[6,3]->[6,4].Note that the described procedure, as a side effect, can repair multiple broken segments, as it happens withthe broken route in Figure 1d and the result of repairing its broken segment that starts at cell [4,2] shown inFigure 1e (ASCII visualizations are shown in Figure 2d and Figure 2e, respectively).3Stage 2 – Full Repair and (15/15 marks)Extend your program from Stage 1 to repair all broken segments in a route and handle multiple changes of blockpositions in the grid. Each new configuration of blocks will be provided from stdin following after input linewith a single character $. Once a new configuration of blocks is loaded (given in the format described underStage 0), reassess the status of the most recently processed route, either the route resulting from Stage 1 or thelast repair in Stage 2. If this route has the status of 4, iteratively apply the repair procedure from Stage 1, eachtime on the first broken segment in the route, either until no more broken segments remain or the next segmentcannot be repaired due to the configuration of blocks. If the route was broken and successfully repaired, print thegrid with the route before the repair, after the repair, and the repaired route and its status. Otherwise, only printthe grid with the valid route. If the route was broken and could not be repaired, print the grid with the brokenroute and this message: The route cannot be repaired!. For the exact format of output for Stage 2 seeoutput files test2-out-mac.txt and test3-out-mac.txt generated for test2.txt and test3.txt.Beyond the Scope of the ProjectUse your creativity and extended ASCII and/or UTF characters to print the grids in a fun, artistic, or some othercool way, and share with us your masterpiece grids. Note that this part of the project should not be submitted.The boring stuff…This project is worth 15% of your final mark. A rubric explaining the marking expectations is provided on theFAQ page. You need to submit one program for assessment; detailed instructions on how to do that will beposted on the FAQ page. Submission will not be done via the LMS; instead you will need to log in to a Unixserver and submit your files to a software system known as submit. You can (and should) use submit bothearly and often – to get used to the way it works, and also to check that your program compiles correctly on ourtest system, which has some different characteristics to the lab machines. Failure to follow this simple adviceis highly likely to result in tears. Only the last submission that you make before the deadline will be marked.Marks and a sample solution will be available on the LMS before Tuesday 5 November.Academic Honesty: You may discuss your work during your workshop, and with others in the class, but whatgets typed into your program must be individual work, not copied from anyone else. So, do not give hard copyor soft copy of your work to anyone else; do not “lend” your “Uni backup” memory stick to others for anyreason at all; and do not ask others to give you their programs “just so that I can take a look and get some ideas,I won’t copy, honest”. The best way to help your friends in this regard is to say a very firm “no” when they askfor a copy of, or to see, your program, pointing out that your “no”, and their acceptance of that decision, is theonly thing that will preserve your friendship. A sophisticated program that undertakes deep structural analysisof C code identifying regions of similarity will be run over all submissions in “compare every pair” mode.Students whose programs are so identified will either lose marks through the marking rubric, or will be referredto the Student Center for possible disciplinary action without further warning. This message is the warning. Seehttps://academicintegrity.unimelb.edu.au for more information. Note that solicitation of solutions viaposts to online forums or marketplaces, whether or not payment is involved, is also Academic Misconduct. In thepast students have had their enrollment terminated for such behavior. The FAQ page contains wording for anAuthorship Declaration that you **must** include as a comment at the top of your submitted program.A significant fraction of the marks will be deducted if you do not do so.Deadline: Queries about this specification should be sent to [email protected]. Studentsseeking extensions for medical or other “outside my control” reasons should email [email protected] soon as possible after those circumstances arise. Programs not submitted by 10:00am on Monday 21 Octoberwill incur penalty marks at the rate of two marks per day or part day late. If you attend a GP or other healthcare service as a result of illness, be sure to take a Health Professional Report (HPR) form with you (get it fromthe Special Consideration section of the Student Portal), you will need this form to be filled out if your illnessdevelops in to something that later requires a Special Consideration application to be lodged. You should scanthe HPR form and send it with any non-Special Consideration assignment extension requests.Remember, algorithms are fun! And yes, this document was produced
using LATEX ;)c The University of Melbourne, 2019. The project was prepared by Artem Polyvyanyy, [email protected]
