Hot Topics
Company Based – Codewindow
Nagarro Question Solved | King George’s Rescue | Codewindow.in
A palace has been invaded and its former ruler king George has been imprisoned in in his own Palace. George’s minister William must rescue him,But he must stay clear off the soldiers who have been planted in the palace.
The entrance of the palace is denoted by 1 and the prison where the king has been captured is denoted by 2. the places where soldiers are planted, are denoted by -1 and rest all the places are denoted by 0 .William can travel only in the four directions. given the palace structure is in the form of a a 2D array, your task is to help William find and return the shortest path to rescue king George.
Note
1. if there exists no path from the entrance to the prison, return -1.
2.The palace has only one entrance and a prison,Soldiers are not present at the entrance and at the prison cell.
Input Specification:
Input1: An integer value denoting the number of rows in input3.
Input2: An integer value denoting the number of columns in input3.
Input3: A 2D integer array of size input1 * input2 representing the structure of the palace.
Output Specification:
Return an integer denoting the length of the shortest path that William must find to rescue King George,including the entrance and the prison cell.
Example 1:
Input1: 4
Input2: 4
Input3: {{1, -1, -1,-1},{0,0,0,0},{0,0,-1,0},{0,0,-1,2}}
Output: 7
Example 2:
Input1: 5
Input2: 5
Input3: {{1, -1, -1,-1,-1},{0,-1, -1,-1,-1},{0,-1,0,0,0},{0,-1,0,-1,0},{0,0,0,-1,2}}
Output: 13
Explaination:
William follows the path shown in the figure. there exist other paths as well but the length of the shortest one must be considered which is 13 in this case. therefore 13 will be returned as the output.
Explaination:
William follows the path shown in the figure. there exist other paths as well but the length of the shortest one must be considered which is 7 in this case. therefore 7 will be returned as the output.
Input:
5
5
{{1, -1, -1,-1,-1},{0,-1, -1,-1,-1},{0,-1,0,0,0},{0,-1,0,-1,0},{0,0,0,-1,2}}Output:
13Python
TEST CASE 1:
# Python3 Code implementation for above problem
# QItem for current location and distance
# from source location
grid = [['1', '-1', '-1', '-1'],
['0', '0', '0', '0'],
['0', '0', '-1', '0'],
['0', '0', '-1', '2']]
class QItem:
def __init__(self, row, col, dist):
self.row = row
self.col = col
self.dist = dist
def __repr__(self):
return f"QItem({self.row}, {self.col}, {self.dist})"
def minDistance(grid):
source = QItem(0, 0, 0)
# Finding the source to start from
for row in range(len(grid)):
for col in range(len(grid[row])):
if grid[row][col] == '1':
source.row = row
source.col = col
break
# To maintain location visit status
visited = [[False for _ in range(len(grid[0]))]
for _ in range(len(grid))]
# applying BFS on matrix cells starting from source
queue = []
queue.append(source)
visited[source.row][source.col] = True
while len(queue) != 0:
source = queue.pop(0)
# Destination found;
if (grid[source.row][source.col] == '2'):
return source.dist
# moving up
if isValid(source.row - 1, source.col, grid, visited):
queue.append(QItem(source.row - 1, source.col, source.dist + 1))
visited[source.row - 1][source.col] = True
# moving down
if isValid(source.row + 1, source.col, grid, visited):
queue.append(QItem(source.row + 1, source.col, source.dist + 1))
visited[source.row + 1][source.col] = True
# moving left
if isValid(source.row, source.col - 1, grid, visited):
queue.append(QItem(source.row, source.col - 1, source.dist + 1))
visited[source.row][source.col - 1] = True
# moving right
if isValid(source.row, source.col + 1, grid, visited):
queue.append(QItem(source.row, source.col + 1, source.dist + 1))
visited[source.row][source.col + 1] = True
return -1
# checking where move is valid or not
def isValid(x, y, grid, visited):
if ((x >= 0 and y >= 0) and
(x < len(grid) and y < len(grid[0])) and
(grid[x][y] != '-1') and (visited[x][y] == False)):
return True
return False
# Driver code
if __name__ == '__main__':
print("-1" if minDistance(grid) == -1 else minDistance(grid)+1)TEST CASE 2:
# Python3 Code implementation for above problem
# QItem for current location and distance
# from source location
grid = [['1', '-1', '-1', '-1','-1'],
['0', '-1', '-1', '-1','-1'],
['0', '-1', '0', '0','0'],
['0', '-1', '0', '-1','0'],
['0', '0', '0', '-1','2']]
class QItem:
def __init__(self, row, col, dist):
self.row = row
self.col = col
self.dist = dist
def __repr__(self):
return f"QItem({self.row}, {self.col}, {self.dist})"
def minDistance(grid):
source = QItem(0, 0, 0)
# Finding the source to start from
for row in range(len(grid)):
for col in range(len(grid[row])):
if grid[row][col] == '1':
source.row = row
source.col = col
break
# To maintain location visit status
visited = [[False for _ in range(len(grid[0]))]
for _ in range(len(grid))]
# applying BFS on matrix cells starting from source
queue = []
queue.append(source)
visited[source.row][source.col] = True
while len(queue) != 0:
source = queue.pop(0)
# Destination found;
if (grid[source.row][source.col] == '2'):
return source.dist
# moving up
if isValid(source.row - 1, source.col, grid, visited):
queue.append(QItem(source.row - 1, source.col, source.dist + 1))
visited[source.row - 1][source.col] = True
# moving down
if isValid(source.row + 1, source.col, grid, visited):
queue.append(QItem(source.row + 1, source.col, source.dist + 1))
visited[source.row + 1][source.col] = True
# moving left
if isValid(source.row, source.col - 1, grid, visited):
queue.append(QItem(source.row, source.col - 1, source.dist + 1))
visited[source.row][source.col - 1] = True
# moving right
if isValid(source.row, source.col + 1, grid, visited):
queue.append(QItem(source.row, source.col + 1, source.dist + 1))
visited[source.row][source.col + 1] = True
return -1
# checking where move is valid or not
def isValid(x, y, grid, visited):
if ((x >= 0 and y >= 0) and
(x < len(grid) and y < len(grid[0])) and
(grid[x][y] != '-1') and (visited[x][y] == False)):
return True
return False
# Driver code
if __name__ == '__main__':
print("-1" if minDistance(grid) == -1 else minDistance(grid)+1)
Automata Fixing
Popular Category
Hot Topics
Company Based – Codewindow