The Delivery of Control

Description
The Gugoo Gang controls an area of N × M blocks in a city. To award Tom for his contribution to the Gugoo, the Boss decides to turn over part of the area under his control to Tom. The delivery is done according to the Gang's old tradition.

Tom is asked to start a trip at a cross in the city, take a ride along the streets, and finally get back to his start point within T minutes. In every minute Tom may move from one cross to an adjacent one. The blocks enclosed by his route are delivered to him. During the trip, Tom is not allowed to come back to a cross which he has already visited except the start point and once he reaches the start point his trip ends. If Tom fails to get back in time, he won't get any block. And he can not give up any blocks that is enclosed by his route.
As an environment protectionist, Tom assigns a satisfaction value to each block according to its greenness. He wants to maximize the sum of satisfaction values of his blocks.
Input
The first line contains three integers, N, M and T (1 ≤ N, M, T ≤ 20).
N × M integers follow which describe the satisfaction values of every block.
Output
One line contains the maximum sum.
Sample Input
4 4 10
-1 2 1 1
2 -1 0 2
3 1 -1 1
2 2 1 -1
Sample Output
10

as

1个回答

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!