12 人解决，21 人已尝试。
14 份提交通过，共有 40 份提交。
6.1 EMB 奖励。
2441. Legendary Brave, TOKOSHI
单点时限: 3.0 sec
内存限制: 256 MB
This is a story of a fantasy world, Sword and Magic world. There are so many monsters and magics and miracles. There is a legendary prophecy, “When the darkness tends to cover all over the worlds, a legendary brave appears and light is brought about”. Such a prophecy is becoming actual. That is, the Devil woke up from the sleep in 1024. The devil kill the half of the total population in the world to the moment. But the legendary brave man did not appeared. Is the world changed into the darkness world by the devil as it is?
No, the light world should be saved. That is, the legendary brave have already appeared. But the legendary brave was not fighting with the devil. The name of the legendary brave is SOTA Tokoshi. He loves a woman better than anyting. But a time for him to get serious has come. He is found by the king and has to defeat the devil at last. This world is as a “figre: 1” shown below. The starting position is the left-upper corner and the devil’s castle is the right-down corner. He can move only 4 dirctions, up, down, right , left.
However, he does not give up girl hunting’s because of such a thing. He decided to go to the devil’s castle through the way which the most girls can hunt. But he hate to take a roundabout way. So he decided to go to the devil’s castle by a shortest path. How many girls can he hunt in such case? However, occasionally, he may mistake and may hunt a man. So your task is to find a shortest path to the devil’s castle in which the maximum value which the number of hunted women to the number of hunted men is subtracted. Following “figure: 2” is the answer of first sample input.
输入格式
Input consists from multiple test cases. The first line of each test case contains two positive integers r and c less than 1024 separated by a single space. The r means the height of map and c means width of map. Following r lines contains c integers less than 1024 in absolute value separated by a single space. These integers indicate how many women and men can Tokoshi get. Positive number means Tokoshi get the women and negative number means Tokoshi get the men. Input is terminated by EOF.
输出格式
For each test case, you are to print “Case X: Y” for each line. X is the number of the test case starting with 1 for the first test case and incrementing by 1 for successive test case. Y is the answer of the question.
Note for C++
You should at least use scanf() and printf() to take input and produce output for this problem. cin and cout is too slow for this problem to get it within time limit. Sorry for this but otherwise it becomes impossible for us to set a reasonable time limit.
样例
Input
3 3 1 3 0 1 -1 -3 -2 -1 0 2 2 0 0 0 0
Output
Case 1: 2 Case 2: 0
题目标签