Suppose there is a maze given in the form of an undirected graph G(V, E). There are r number of rats stuck inside the maze precisely at the same location, say a vertex s. Now, the rats can only move at night (since the maze is inside the false ceiling of Mr. Mortein\'s house and if the rats move during day, he will find them and shoot at them). Every night, a rat can move from one endpoint of an edge to another. However, for any edge e in the maze, only c(e) rats can move together in one night including both directions (otherwise the noise would be loud enough to wake Mr. Mortein up). All the rats want to escape the maze through the exit location t. Given an integer k, your job is to decide whether all rats can escape by at most k nights. Can you design an algorithm to solve this problem ? (Ideally, the runtime should be O(rk(V + E)), although anything polynomial in r, k, V, E would be fine. You do not need to formally prove correctness but give a clear description of the construction and a brief justification of why this should work

Answer rating: 100% (QA)

SOLUTION ALGORITHM 1If rodent arrives at the goal print the arrangement grid Else Imprint the presen... View the full answer