You are in a new city C where all the streets in this city cross each other at different points.

Your goal is to find out the length of the shortest path to walk from building A to building B $($in

miles$).$ The city has the following layout:

$$ Street S $=[$index$,$ layout, is one way, width, length$]$

$$ Index: an integer from $0$ to $($N $1)$ that represents the index of the street in the city$$s

layout. Note that two different streets $($with vertical and horizontal layout$)$ may have

the same street$$s index.

$$ Layout: an integer value represented by $(0$ or $1)$ defining the layout of the street in

relation to other streets in the city.

$$ Value $0$: vertical street

$$ Value $1$: horizontal street

$$ Is one way: an integer value represented by $(0$ or $1)$ that defines whether the street is

one$-$way or not

$$ Value $0$: False

$$ Value $1$: True

$$ Width: a decimal value that represents the width of the street in miles, from the left

side to right side of the street.

$$ Length: an decimal value that represents the length of the street in miles, from the

starting point to the end point of the street.

$$ Building X $=[$street$,$ position, location$]$

$$ Street: a street S representing the street where the building is located

$$ Position: an interger value represented by $(0$ or $1)$:

$$ Value $0$: right side of the street

$$ Value $1$: left side of the street

$$ Location: An interger value represented by $(0,1,2)$:

$$ Value $0$: the building is located at the start of the street

$$ Value $1$: the building is located at the middle of the street

$$ Value $2$: the building is located at the end of the street

$$ P erson P $=[$BX $,$ BY $,$ intersection, direction, distance traveled$]$

$$ Bx: Building X is the source building

$$ By: Building Y is the destination building

$$ Intersection: the point where two streets intersect represented by a tuple with two streets

$($Sv$,$ Sh$)$ where Sv is a vertical street, and Sh is a horizontal street

$$ Direction: a char value defining the direction this person is taking at any point in the

process.

$$r$$: right

$$l$$: left

$$d$$: down

$$u$$: up

$$ Distance traveled: A decimal value representing the distance traveled so far by this

person.

$$ City Policies:

$$ Streets in City C do not have sidewalks. They only have a median strip where people

can walk down as pedestrians

$$ If a specific street is one$-$way or$/$and a dead$-$end, then this rule applies for pedestrians

too.

$$ Once a person exits from a building, this person must be directed towards the median

strip that is located in front of the building, this walked distance must also be considered

in your final answer.

$$ Once a person has reached the destination, and in order to enter the destination building,

this person must leave the median strip, cross the street and enter the building that will

be located in front of the median strip. This walked distance must also be considered in

your final answer.

The following is an example of an instance of this problem statement:

Given a city C with a list of N streets S$,$ buildings Bx and By$,$ and person P$1$ as follows:

$$ C $=[[0,0,0,5\mathrm{.}00,10\mathrm{.}00],[1,0,1,3\mathrm{.}00,9\mathrm{.}00],[2,0,0,5\mathrm{.}00,5\mathrm{.}00],[0,1,1,7\mathrm{.}00,10\mathrm{.}00],[1,1,0,2\mathrm{.}00,15\mathrm{.}50],$

$[2,1,0,5\mathrm{.}00,12\mathrm{.}50]]$

$$ Bx $=[$C$[0],0,0]$; By $=[$C$[5],1,2]$

$$ P$1=[$Bx$,$ By$,($C$[0],$ C$[3]),$l$,0\mathrm{.}00]$

Find the minimum distance P$1$ needs to travel from Bx to By in city C

$(5$ points$)$ Design an optimized algorithm for this problem using a Dynamic Programming

or$/$and Greedy approach. You can use the example instance of this problem given in the

problem statement, but you will need to prove that your algorithm works for any instance of

this problem $($not only for the given example$).$ The design of your algorithm must include

diagrams of your city showing every step in your algorithm, and short written step$-$by$-$step

instructions explaining $($at the high level$)$ how your algorithm works. Show ALL your

work to get credit. Algorithm designs using approaches other than Dynamic

Programming or$/$and Greedy won$$t get credit for this homework assignment