Amazon Fresh is a grocery delivery service that offers consumers the option of purchasing their groceries online and having them delivered on schedule. The Amazon Fresh team is planning a route for a delivery truck to deliver customer orders in the city of Techlandia. The planner will create a delivery area for each order to effectively plan the route. The area is abstracted as a grid. Not all locations are accessible by road. The truck only needs to make a single delivery.

write an algorithm to determine the minimum distance required for the truck to deliver the order.

Assumptions:

Some places in the delivery area cannot be accessed by the driver, as there are no roads in those locations.

The delivery area can be represented as a two dimensional grid of integers, where each Integer represents one cell.

The truck must start from the top-left corner of the area, which is always accessible and can move one cell up, down, left or right at a

time.

The truck must navigate around the areas without roads and cannot leave the area. The accessible areas are represented as 1, areas without roads are represented by 0 and the order destination is represented by 9.

Input

The input to the function/method consists of

one argument:

area, representing the two dimensional grid of integers.

Output

Return an integer representing the total distance traversed to deliver the order else

return -1.

Constraints

1<=rows, columns <=10^3

Example

Input:

area =

[[1, 0, 0],

[1, 0, 0],

[1, 9, 1]]

Output:

3

Explanation:

Starting from the top-left corner, the truck traversed the cells (0,0) - (1,0)-> (2,0) -- (2,1). The truck traversed the total distance to deliver the order

So, the output is 3,

Answer:

Code:

from collections import deque

# To store the cell coordinates
class Point:
    def __init__(self, x: int, y: int):
        self.x = x
        self.y = y



#queue data strcuture
class queueNode:
    def __init__(self, pt: Point, dist: int):
        self.pt = pt  # cell's coordinates
        self.dist = dist  # Cell's distance from the source


#direction arrays to get the four directions(up,down,left,right)
rowNum = [-1, 0, 0, 1]
colNum = [0, -1, 1, 0]

# Function "Shortest_Route" to find the shortest path between
# a given source cell to a destination cell.

def Shortest_Route(area, src: Point):
    ROW = len(area)
    COL = len(area[0])
    visited = [[False for i in range(COL)] for j in range(ROW)]

    visited[src.x][src.y] = True

    # Create a queue for Shortest_Route
    q = deque()

    # Distance of source cell is 0 because starting point is at a Distance of 0 from itself
    s = queueNode(src, 0)
    q.append(s)  # append source cell

    # Perform a Shortest_Route starting from source cell
    while q:

        curr = q.popleft()  # pop the front cell

        # If we have reached the destination cell,then return the current distance+1
        pt = curr.pt
        if area[pt.x][pt.y] == 9:
            return curr.dist+1

        # Otherwise append its adjacent cells i.e the four directions from the current cell
        for i in range(4):
            row = pt.x + rowNum[i]
            col = pt.y + colNum[i]

            # if adjacent cell is valid, has path and not visited yet, append it.
            if (area[row][col] >= 1 and
                    not visited[row][col]):
                visited[row][col] = True
                Adjcell = queueNode(Point(row, col), curr.dist+1)
                q.append(Adjcell)

    #If destination cannot be reached return -1;
    return -1

def main():
    R = int(input("Enter the number of rows:")) 
    C = int(input("Enter the number of columns:")) 
  
    # Initialize the area matrix 
    area = [] 
    print("Enter the entries rowwise:") 
  
    # For user input 
    for i in range(R):          # A for loop for row entries 
        a =[] 
        for j in range(C):      # A for loop for column entries 
            a.append(int(input())) 
        area.append(a) 
    
    # source node
    source = Point(0, 0)
    
    #call the Shortest_Route Function 
    dist = Shortest_Route(area, source)
    #print the minimum distance required
    print("The distance is : "+str(dist))

main()

Output:

PFA