Algorithm Final Course Project

Finding a route across a rainy city grid, for my algorithms course.

What I built

This was my final Algorithms and Data Structures assignment at the University of Bologna in 2022/2023. Given a city grid, the program finds a route around buildings while accounting for the shelter they provide from rain. I wrote it in C and had to keep it fast enough for the larger maps.

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

Rain-aware shortest-path program screenshot 1

More screenshots (1)

Rain-aware shortest-path program screenshot 2

Built with

Language: Pure C.
Focus: Algorithm optimization, memory management, graph traversal.

Source: GitHub