Today we got an assignment to complete in lab (in two hours). The question was:
- You're given an m*n matrix.
- The matrix has 'h' residential halls and 'b' main building entrances.
- The location of these 'h' halls and 'b' entrances is known (in terms of (x,y) coordinates).
- You need to lay pathways such that every residential hall has at least one way to reach one of the 'b' entrances.
- There can be at most 'b' such disconnected pathways.
- The length of the pathway must be minimum.
- You can only move up, down, left or right.
- The solution must not be a brute force attempt.
The assignment is over. But I'm still thinking how this would be solved. Is there a standard term for such problems? What should I read up?
Do people use such algorithms to laying roads in cities as well?