Castle on the grid| Queue
TASK(medium)
You are given a square grid with some cells open (.) and some blocked (X). Your playing piece can move along any row or column until it reaches the edge of the grid or a blocked cell. Given a grid, a start and a goal, determine the minmum number of moves to get to the goal.
Example.
Grid=[‘…’,’.X.’,’…’]
startX=0
startY=0
startX=1
goalY=2
The grid is shown below:
...
.X.
...
The starting position (startX,startY)=(0,0) so start in the top left corner. The goal is (goalX,goalY)=(1,2). The path is (0,0)->(0,2)->(1,2). It takes 2 moves to reach the goal.
Function Description
Complete the minimumMoves function in the editor.
minimumMoves has the following parameter(s):
- string grid[n]: an array of strings that represent the rows of the grid
- int startX: starting X coordinate
- int startY: starting Y coordinate
- int goalX: ending X coordinate
- int goalY: ending Y coordinate
Returns
- int: the minimum moves to reach the goal
Input Format
The first line contains an integer n, the size of the array grid.
Each of the next n lines contains a string of length n.
The last line contains four space-separated integers, startX,startY,goalX, goalY.
Constraints
1<=n<=100
0<=startX,startY,goalX,goalY<n
Sample Input
STDIN FUNCTION
----- --------
3 grid[] size n = 3
.X. grid = ['.X.','.X.', '...']
.X.
...
0 0 0 2 startX = 0, startY = 0, goalX = 0, goalY = 2
Sample Output
3
SOLUTION 1
def minimumMoves(grid, startX, startY, goalX, goalY):
# Create an array of arrays on integers to represent the grid
grid_array = []
for x in grid:
new_x = []
for char in x:
match char:
case ".":
new_x.append(101)
case "X":
new_x.append(-1)
grid_array.append(new_x)
SOLUTION 2
# Traverses the entire array from the startting cell
# calculating the amount of steps needed to reach
# each cell and records the result in the array
grid_array[startX][startY] = 0
x_len = len(grid_array[0])
y_len = len(grid_array)
current_cells = [[startX, startY]]
next_value = 1
while current_cells:
next_cells = []
for cell in current_cells:
x = cell[0]
y = cell[1]
if y < x_len - 1:
for y_ in range(y + 1, x_len):
if grid_array[x][y_] < next_value:
break
grid_array[x][y_] = next_value
next_cells.append([x, y_])
if y > 0:
for y_ in range(y - 1, -1, -1):
if grid_array[x][y_] < next_value:
break
grid_array[x][y_] = next_value
next_cells.append([x, y_])
if x < y_len - 1:
for x_ in range(x + 1, y_len):
if grid_array[x_][y] < next_value:
break
grid_array[x_][y] = next_value
next_cells.append([x_, y])
if x > 0:
for x_ in range(x - 1, -1, -1):
if grid_array[x_][y] < next_value:
break
grid_array[x_][y] = next_value
next_cells.append([x_, y])
current_cells = next_cells
next_value += 1
# Returns the amount of steps needed to reach the goal cell
return grid_array[goalX][goalY]
EXPLANATION STEPS
1. Initialization:
- Read and parse the input grid.
- Identify the starting position (0,0) and the ending position (n-1,n-1).
2. Breadth-First Search (BFS):
- Use a queue to explore each cell and track the number of moves taken to reach that cell.
- Initialize the queue with the starting position (0,0) and a move count of 0.
3. Exploration:
- Dequeue the current cell (r, c) from the queue.
- Explore all possible movements (up, down, left, right) from the current cell:
- Check if the new cell is within bounds and not blocked ('.').
- If valid, mark the cell as visited by marking it as blocked ('X') to prevent re-visiting.
- Enqueue the new cell with an incremented move count.
- Stop the BFS when you dequeue the ending position (n-1,n-1). The number of moves at this point gives the shortest path.
4. Output:
- Print the number of moves required to reach the ending position (n-1,n-1).
