Room Evacuation

This problem gives us an ASCII description of a room, with people and exits, and asks us how many people can reach an exit in an allotted time.

The input size of 20x20, and the intuitive understanding of a "choke point" in the graph strongly indicate that this is a flow problem. We can naturally create a node for each NxM pair, at each time t. We split each node to in-out nodes, with a traversal of 1, to guarantee only a single person traverses a node at any time. We set source nodes at time t=0 to any location that has a person starting, and each exit node has a flow of 1 to a sink at every time interval. We compute the maxflow to the sink to see how many can reach the exit.

While the node count is high, the graph structure is such that the runtime should be fast enough.