PROBLEM LINK:
DIFFICULTY:
MEDIUM
PREREQUISITES:
Graphs, greedy algorithms
PROBLEM:
Our aim is to clean maximum squares within the given time.
EXPLANATION:
Ok, let’s start from the starting point. We move away from the starting point, initially in a direction from which it would take us the shortest distance to return to our starting point than in a direction which is farther from the starting point because we anyways need to return back for charging the battery of the vacuum cleaner. For example, if the map is as shown in the image, we’ll prefer path 2 than path 1 because we can clean more squares in path 2 and return back easily than in path 1. Although we might not be able to clean some squares because our charge has already lost, we can certainly save our time.
