Name:Unknown
Clan:Unknown
Member Since:Nov 2024
Last Seen:May 2025
Profiles:
Following:0
Followers:0
Allies:0
You are given a 2D grid representing a maze, where:
0 represents an open cell,
1 represents a wall,
S represents the starting point,
E represents the endpoint.
- Your task is to find the shortest path from the starting point S to the endpoint E. You can move up, down, left, or right, but you cannot move through walls (1). If there is no path, return None.
Input:
A list of lists (2D grid) representing the maze.
Output:
A list of tuples representing the coordinates of the path from S to E, or None if no path exists.
def find_shortest_path(maze):
passdef test_find_shortest_path():
maze1 = [
['S', '0', '1', '0', '0'],
['0', '0', '1', '0', '1'],
['1', '0', '0', '0', '0'],
['0', '1', '1', '1', 'E']
]
assert find_shortest_path(maze1) == [(0, 0), (1, 0), (1, 1), (2, 1), (2, 2), (2, 3), (2, 4), (3, 4)]
maze2 = [
['S', '1', '0'],
['0', '1', '0'],
['0', '0', 'E']
]
assert find_shortest_path(maze2) == [(0, 0), (1, 0), (2, 0), (2, 1), (2, 2)]
maze3 = [
['S', '1', '1'],
['1', '1', '1'],
['1', '1', 'E']
]
assert find_shortest_path(maze3) is None
print("All tests passed!")
# Uncomment to run tests
# test_find_shortest_path()Problem Statement:
You are given a 2D grid (matrix) of integers where each cell represents a number. Your task is to find the maximum sum of a path from the top-left corner to the bottom-right corner of the grid. You can only move right or down at any point in time. However, there is a twist: certain cells are "blocked" and cannot be traversed. The blocked cells are represented by a special value (e.g., -1).
Requirements:
- Implement a function max_path_sum(grid: List[List[int]]) -> int that takes a 2D list of integers as input.
- The function should return the maximum sum of the path from the top-left corner to the bottom-right corner, or -1 if there is no valid path.
- The grid will contain:
- Positive integers (representing valid cells).
- "-1" (representing blocked cells).
- The grid will have at least one row and one column, and at most 100 rows and 100 columns.
- You must optimize your solution to handle the maximum grid size efficiently.
from typing import List
def max_path_sum(grid: List[List[int]]) -> int:
if not grid or not grid[0]:
return -1
rows, cols = len(grid), len(grid[0])
# Create a 2D list to store the maximum sums
dp = [[-1] * cols for _ in range(rows)]
# Initialize the starting point
if grid[0][0] != -1:
dp[0][0] = grid[0][0]
# Fill the dp table
for i in range(rows):
for j in range(cols):
if grid[i][j] == -1:
continue # Skip blocked cells
# If we can come from the top
if i > 0 and dp[i-1][j] != -1:
dp[i][j] = max(dp[i][j], dp[i-1][j] + grid[i][j])
# If we can come from the left
if j > 0 and dp[i][j-1] != -1:
dp[i][j] = max(dp[i][j], dp[i][j-1] + grid[i][j])
# The result is in the bottom-right corner
return dp[rows-1][cols-1]def test_max_path_sum():
# Test case 1: Basic valid path
grid1 = [
[5, 3, 2, 1],
[1, -1, 1, 1],
[4, 2, 1, 1],
[1, 1, 1, 10]
]
assert max_path_sum(grid1) == 22 # Path: 5 -> 3 -> 2 -> 1 -> 1 -> 1 -> 10
print("Test case 1 passed.")
# Test case 2: Another valid path
grid2 = [
[1, 2, 3],
[4, -1, 6],
[7, 8, 9]
]
assert max_path_sum(grid2) == 27 # Path: 1 -> 2 -> 3 -> 6 -> 9
print("Test case 2 passed.")
# Test case 3: No valid path due to blockage
grid3 = [
[1, 2, 3],
[4, -1, 6],
[-1, -1, 9]
]
assert max_path_sum(grid3) == -1 # No valid path
print("Test case 3 passed.")
# Test case 4: All cells are blocked except start and end
grid4 = [
[1, -1, -1],
[-1, -1, -1],
[-1, -1, 9]
]
assert max_path_sum(grid4) == -1 # No valid path
print("Test case 4 passed.")
# Test case 5: Single cell grid
grid5 = [
[5]
]
assert max_path_sum(grid5) == 5 # Only one cell
print("Test case 5 passed.")
# Test case 6: Larger grid with a valid path
grid6 = [
[1, 2, 3, 4],
[5, 6, -1, 8],
[9, 10, 11, 12],
[13, 14, 15, 16]
]
assert max_path_sum(grid6) == 66 # Path: 1 -> 2 -> 3 -> 4 -> 8 -> 12 -> 16
print("Test case 6 passed.")
# Test case 7: All positive numbers with no blockages
grid7 = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
]
assert max_path_sum(grid7) == 21 # Path: 1 -> 2 -> 3 -> 6 -> 9
print("Test case 7 passed.")
# Test case 8: Large grid with a