Python program to find the shortest safe route in a path with landmines

In this Python tutorial, we will go through the program to find the length of the shortest safe route possible from a safe cell in the first column of the matrix to a safe cell in the last column. The condition for the safe route is that we have to avoid the landmines placed randomly in the rectangular matrix.

Conditions: 

• Cells marked with ‘0’ and their adjacent cells (left, right, above, and below) are to be avoided while traversing through the matrix as they all are unsafe cells.
•  Diagonal moves are not allowed, we can only move through the edge of any cell of the matrix.

Breadth-First Search

We will use the breadth-first search algorithm to solve this traversal problem. This approach is optimal as the time complexity is linear in the form of O(m*n).

import sys
from collections import deque

# class for storing pair of numbers
class Pair:
    def __init__(self, first, second):
        self.first = first
        self.second = second


# checks if x & y doesn't exceed row and col constraint of matrix
def isInsideRangeOfMatrix(x, y):
    if (x >= row or y >= col or x < 0 or y < 0):
        return False
    return True

def findShortestPathBetweenColumns(mat, row, col):
    # Set value of all the neighbouring cells of the cells having landmine as min value or marker
    marker = sys.maxsize
    for i in range(row):
        for j in range(col):
            if (mat[i][j] == 0):
                for k in range(4):
                    if (isInsideRangeOfMatrix(i + rowDir[k], j + colDir[k])):
                        mat[i + rowDir[k]][j + colDir[k]] = marker
    # Replace those marker value with 0
    for i in range(row):
        for j in range(col):
            if (mat[i][j] == marker):
                mat[i][j] = 0

• We will first import deque (Doubly Ended Queue) from the collections module. This will allow us to do quicker append and pop operations from both the ends of the container, with a time complexity of O(1) as compared to O(n) time complexity in the case of a list.
• We will create a class called pair to define the properties of a cell in the matrix in the form of its rows and columns. We will then assign the first as the row number and the second as the column number using the __init__ function. 
• Next, we will define a function to check if a cell is inside the range of m or not, with the help of the number of rows and columns in the matrix.   

Defining the function to find the shortest path:

• If a cell with a landmine is found, we will mark all its adjacent cells as unsafe as well using a for loop. After marking those cells, we will also replace the value within the cells with 0. 
• We will then create a boolean matrix with a similar dimension to store info about cells already visited in the current route.

See the Python code below:

# dist[i][j] stores minimum distance from first column to ith row and jth column cell
# initialized with -1 which indicates paths are not found
dist = [[-1 for i in range(col)] for j in range(row)]

# queue is being used to implement BFS (breadth first search) and stores pair of numbers
# where first indicates curr row and second indicates curr column
queue = deque()
'''
    All the elements in first column having value 1 is considered as source
    and all those elements are added into queue 
    as these will be the first level elements in the queue in level order traversal.
    As these elements are source, dist till ith row and 0th col will be 0
    and hence, dist[i][0] is marked as 0 for all possible i
'''
for i in range(row):
    if mat[i][0] == 1:
        queue.append(Pair(i,0))
        dist[i][0] = 0

'''
    1. Remove the first element from the queue
    2. All the elements present in the queue are updated with minimum dist
    3. For all the neighbouring elements where it's possible to move i.e, mat[next_x][next_y] == 1
       and dist is not updated i.e, dist[next_x][next_y] == -1
       (which means that this was the first parent in the level order traversal trying to update it's child
        which in turn means that the distance will actually be minimum),
       update dist of it's child node i.e, dist[next_x][next_y] = curr_dist + 1
       where curr_dist is distance till the parent node
       and add these elements in the queue
'''
while len(queue) > 0:
    curr_pair = queue.popleft()
    curr_dist = dist[curr_pair.first][curr_pair.second]
    curr_x = curr_pair.first
    curr_y = curr_pair.second
    for k in range(4):
        next_x = curr_x + rowDir[k]
        next_y = curr_y + colDir[k]
        if (isInsideRangeOfMatrix(next_x, next_y) and dist[next_x][next_y] == -1 and mat[next_x][next_y] == 1):
            dist[next_x][next_y] = curr_dist + 1
            queue.append(Pair(next_x, next_y))

ans = sys.maxsize
# Take minimum of all the distances which can reach to the last column
for i in range(row):
    if dist[i][col-1] != -1:
        ans = min(ans, dist[i][col-1])

if ans == sys.maxsize:
    print("No possible paths found between first column and last column.")
else:
    print("Length of shortest path between first column and last column is ", ans)

Breadth-first search algorithm

1. We will initialize the deque() container and assign it to the variable named queue, and for any safe cell found in the first column, we will append its indices to the queue. Also, we will update the distance from -1 to 0 as we can traverse forward from this cell now.
2. Then we will use a while loop to update the current queue back to an empty queue, its distance back to -1, and get the coordinates of the cell already visited. Inside the while loop, we will use a for loop to check if any of the adjacent cells is safe, move to that cell, and update the dist with an increment of 1 and subsequently append the queue. 
3. Within the main scope of the shortest path definition, we will check if we have reached the last cell of the matrix and the distance is not equal to -1. If so, we will collect the shortest route in ‘ans’ variable as the minimum of distance incremented through the traversal and the maxsize attribute of the sys module.
4. Finally, we can call the findShortestPath function with a matrix of certain dimensions as the parameter. Here, we will initialize a matrix of 4×4, and call the function.

# row denotes no of rows
# col denotes no of columns
row = 4
col = 4

'''
 4 Directions - North, West, East, South
 North - (-1, 0)
 West  - (0, -1)
 East  - (0, 1)
 South - (1, 0)
 rowDir stores change in row value of north, west, east & south directions respectively
 colDir stores change in col value of north, west, east & south directions respectively
'''
rowDir = [-1, 0, 0, 1]
colDir = [0, -1, 1, 0]

# input matrix
matrix = [[1, 1, 0, 0],
        [1, 1, 1, 1],
        [1, 1, 1, 1],
        [0, 1, 1, 1]]

# Find shortest path between first column and last column
findShortestPathBetweenColumns(matrix, row, col)

Output:

Length of shortest path between first column and last column is  4

Read More: How to implement Breadth First Search algorithm in Python