代写program程序、Java、Python编程代写

日期：2021-10-03 11:08

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: ##.#.#