Algorithm Final Course Project

What I built

This was the final assignment for my Algorithms and Data Structures course at the University of Bologna in 2022/2023. The input is an N x M city map whose traversal costs can change; the job is to find the cheapest path without letting large maps grind to a halt.

The Challenge

A pedestrian 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