The solution is straightforward. It is sufficient to record the number of people in the tram, and find out the maximum value.
This turns out to be a simple problem if one has noticed that there exists at most one wolf around any pig. Thus, it is not necessary to consider the case where some single pig can be eaten by multiple wolves. We can enumerate each wolf and check whether there is at least one pig around it.
We can find that there are multiple connected components, and then implement DFS or BFS to each component, starting from the node which does not have any superior nodes, to calculate the maximum depth. This is just the required answer.
Note that once we move to the lower floor, we can never return back. Thus, we must clean up all the weeds on the current floor, and then move downstairs.
For each floor, we denote the positions of the leftmost weed and the rightmost weed as pl and pr, respectively. Then, suppose that we reach the current floor at some position p. No matter which direction we are facing to, the minimum distance that we need to move is either |p - pl| or |p - pr|, and finally we stay at either pl or pr. Now, we find the next floor that has at least one weed (note that there might be several floors without any weeds during our moving).
After finding the next floor, we can find that we should move from the previous position to the leftmost weed or rightmost weed in “horizonal” direction, according to whether we face to the same direction or not. The above calculation resembles the Manhattan Distance, whose horizational distance and vertical distance can be independently computed.
Well, I think this is really a brain-storm problem. When I finally understand the tutorials, I feel that I have seen a new world...
Let us first consider that we have 1 × m empty cells. If we only focus on the horizonal pipelines, it can be seen that the pattern can only be either “LRLRLRLRL...” or “RLRLRLRLRL...”, where “R” means that the pipeline is connected to the right side while “L” means that the pipeline is connected to the left side. For the vertical pipelines, we have 2m patterns, since they will never lead to “leaking” states.
Now, we extend the above case to 2 × m empty cells. Based on similar arguments, for the horizonal pipelines, we have 22 feasible patterns since we have two rows. For the vertical pipelines, one can check that for each column we always have “UD” and “DU”, two patterns, where “U” and “D” denote that the pipeline is connected to the upper and bottom side, respectively.
In general, with n × m empty cells, the answer is 2(m + n). If there are several cells that are not empty, then the patterns of the row and column to which these cells belong in fact have been determined. Suppose that the number of rows and columns that are fully empty is totally t, and then the answer will be 2t. Note that the previously filled cells might have already led to “leaking” states, and thus for this case the answer should be zero.
116B. Little Pigs and Wolves
for the test case
simple enumeration give wrong answer.
But I think your test case is invalid, since the problem says that "The little pigs are afraid of wolves, so there will be at most one wolf adjacent to each little pig."