辅导program程序、Java、Python编程辅导

日期：2021-10-04 07:45

Car Navigation
In this assesment you will develop a navigation system that can be used by a car driver to find a route
from a starting point to his/her destination while navigating a rectangular (Manhattan-like) grid filled with
blockages. All roads can be driven in both directions when they are not blocked. Positions are identified by
integer (x,y) coordinates in zero-based coordinates (i.e., 0...maxX-1, where maxX is the size of the maze in
the x-dimension, similarly maxY). The (0,0) position is in the upper-left corner. At any given moment, the
car can only move 1 step in one of 4 directions provided that the position is without obstacles and lies within
the maze. The car can thus move in the following directions:
Go North: (x,y) -> (x,y-1)
Go East: (x,y) -> (x+1,y)
Go South: (x,y) -> (x,y+1)
Go West: (x,y) -> (x-1,y)
The navigation system should search for a path from the starting position to the destination position (a so
called solution path) until it finds one or until it exhausts all possibilities. In former case it should mark the
path on the map.
The map is represented in the program as a maze. Below you see an example 6x6 input maze, followed by
one with a partial path, and one with a solution path:
S##### S##### S#####
.....# ++++.# ++...#
#.#### #.#### #+####
#.#### #.#### #+####
...#.D ...#.D .++#+D
##...# ##...# ##+++#
The starting position of the car is indicated with the letter ‘S’, the destination is indicated with the letter
‘D’, positions where the car is allowed to drive are indicated with a ‘.’, and obstacles (blocked positions) are
marked with a ‘#’. A position on the path in the maze can be marked by the ’+’ symbol. A path refers
to either a partial path, marked while the system is still searching (i.e., one that may or may not lead to a
solution), or a solution path which leads from start to destination.
It is obvious that when the system is exploring a position it is each time confronted with the same problem:
“find a path to the destination D if the position itself is not D”. It may of course also conclude that the
destination is not reachable from that position. Assume that there is a function findPath(maze, x, y) that
finds a path from some point (x,y) in a maze to a destination. Also suppose that the system reached from
the start to position x=1, y=2 in the maze (by some method). The maze (including the partial path) then
looks as follows:
So the question is then whether there is a path from x=1, y=2 to the destination. If there is then there is
a path from the start to the destination (since a path from the start to x=1, y=2 is already found). To find
a path from position x=1, y=2 to the destination, it can just ask findPath to try to find a path from the
North, East, South, and West of x=1, y=2:
findPath(x=1, y=1) North
findPath(x=2, y=2) East
findPath(x=1, y=3) South
findPath(x=0, y=2) West
Generalizing this, findPath can be called recursively to move from any location in the maze to adjacent
locations. In this way, it moves through the maze. That is, until it has to stop. All the time invalid positions
have to be accounted for. So, a call to go North of the current position, should be disregarded when that
North position is illegal. In order words, base questions are “is the position within the maze (or outside its
bounds)”, and “is the position open (or is it blocked with an obstacle)”? Further the path that is still under
consideration must be marked, and stay marked until it is clear that the destination cannot be reached from
that position. In essence a complete algorithm that finds and marks a path to the destination (if any exists)
and tells us whether a path was found or not (i.e., returns 1 or 0), may look like the following program:
findPath(x, y)
{
if (x,y outside maze) return 0
if (x,y is goal) return 1
if (x,y not open) return 0
mark x,y as part of solution path
if (findPath(North of x,y) == 1) return 1
if (findPath(East of x,y) == 1) return 1
if (findPath(South of x,y) == 1) return 1
if (findPath(West of x,y) == 1) return 1
unmark x,y as part of solution path
return 0
}
In it findPath will be called at least once for each position in the maze that is tried as part of a path. Also,
after going to another position (e.g., North):
if (findPath(North of x,y) == 1) return 1
it is important that the algorithm stops when a path to the destination has been found, i.e., if going North
of x,y finds a path (i.e., returns 1), then from the current position (i.e., current call of findPath) there is
no need to check East, South or West. Instead, findPath just needs to return 1 to the previous call. Path
marking can be done with the ’+’ symbol and unmarking with the ’.’ symbol.
When a no path to the destination can be found from the current position, i.e. findPath fails in all four
directions, then findPath unmarks the current position, and continues searching in the remaining directions
from the previous position. For example, if we’re at x=2, y=3, we first call findPath to North (x=2, y=2).
At x=2, y=2 try all four directions: North x=2, y=1, East x=3, y=2, South x=2, y=3, West x=1, y=2. If
all fail, we backtrack to x=2, y=3 and try East.
To use findPath to find and mark a path from the start to the destination with the given representation of
mazes the main function has to
1. ask the user to input a maze.
2. locate the start position (call it xStart, yStart).
3. call findPath(maze, xStart, yStart).
2 / 5
Task 1. Create inside the main function an array maze with room for 300 characters. Inside the same main
function you should write code that asks the user to input the number of rows and columns of the maze.
These values should be assigned to respectively the local variables maxY and maxX. When the product of maxY
and maxX exceeds 300 then you should print the error message: Number of cells exceeds maximum!
otherwise no text needs to be output.
The output of your program should look as follows:
Number of rows? 200
Number of columns? 4
Number of cells exceeds maximum!
Task 2. Write a function “void inputMaze(char maze[], int maxX, int maxY)” that asks the user to
input maxY strings of maxX characters each. These strings should be stored in the array maze and the strings
should be composed of the following characters:
? ’S’ - starting position.
? ’D’ - destination.
? ’.’ - location where car is allowed to drive.
? ’#’ - location where car is not allowed to drive (obstacle).
The output of your program should look as follows:
Task 3. Write a function “void printMaze(char maze[], int maxX, int maxY)” that prints the maze to the
output. Remember that the values of maxX and maxY indicate the dimensions of the maze.
The output of your program should look as follows:
Number of rows? 6
Number of columns?
Task 4. Write a function “int findStart(char maze[], int maxX, int maxY)” that finds the x and y coordinate
of the starting position in the maze. This point is marked with the character ’S’ in the array maze. Since it
is not possible to return two numbers from a single function, the function should return the value that results
from the following equation: y * maxX + x.
When the array maze contains no starting position, the error message Maze contains no starting point!
should be output. The output of your program should then look as follows:
Number of rows?
Maze contains no starting point!
4 / 5
Task 5. Write a function “int findPath(char maze[], int maxX, int maxY, int x, int y)” that recursively calls
itself and which tries to find a path from the position x, y to the destination. The recursive calls should be
made in such a way that the search from this point is performed in the following order:North, East, South,
and finally West.
The output of your program should look as follows:
Number of rows? 6
Number of columns? 6
Input row 0: S#####
Input row 1: .....#
Input row 2: #.####
Input row 3: #.####
Input row 4: ...#.D
Input row 5: ##...#
When no path is found, the error message No path found! should be output. The output of your program
should look then as follows:
Number of rows? 6
Number of columns? 6
Input row 0: S#####
Input row 1: .....#
Input row 2: #.####
Input row 3: #.####
Input row 4: ...#.D
Input row 5: ##.#.#