John is a tourist from Minas Gerais who is on vacation and wants to explore the cities in UaiSo county. There are 3 main cities that he would like to visit: CheeseBreadLand, DulceDeLecheTown and TorresmoCity, that are painted in blue in the map. But John only moves following a BFS order, and he has time to visit 5 cities only. Help John optimize his trip so he can visit the most possible interesting cities. Consider that the BFS always chooses the neighbors in ascending order and the following map is an undirected graph.
To visit the most cities he would like, what should John do?
a) John should start his trip on city 1, so he can visit 2 cities of interest.
b) John should start his trip on cities 4 or 9, so he can visit 2 cities of interest.
c) John should start his trip on city 3, so he can visit 3 cities of interest.
d) John should start his trip on city 2, so he can visit 2 cities of interest.
e) None of the above
Original idea by: João Vitor Baptista Moreira
No comments:
Post a Comment