Algorithm Final Course Project

Project Description

Developed for the Algorithms and Data Structures course (2022/2023) at the University of Bologna. The goal was to implement a highly efficient algorithm to find the shortest path in a N x M grid-based city map.

The Challenge

A pedestrain must navigate from (0,0) to (N-1, M-1) while:

• Avoiding buildings (marked 1-9 by height)
• Minimizing exposure to rain falling at a 45° angle
• Accounting for building "rain shadows" that cover c cells to the right

Input & Output Format

Input

• Grid size: 10 ≤ N, M ≤ 500
• Cell values: '0' (sidewalk) to '9' (building height)

Output

• Minimum steps d and rain exposure r
• Path sequence (E, O, S, N)
• Returns -1 -1 if unreachable

Implementation Details

The solution requires efficient state management to track position and rain exposure simultaneously.

Keywords

• Dijkstra's Algorithm / BFS
• Dynamic Programming
• Shadow propagation logic
• Memory-efficient grid traversal