Beautiful Meadow 
Time Limit: 5000ms, Special Time Limit:10000ms, Memory Limit:32768KB 
Total submit users: 39, Accepted users: 37 
Problem 10016 :
No special judgement

Problem description 
Tom has a meadow in his garden. He divides it into N * M squares.
Initially all the squares are covered with grass and there may be some squares
cannot be mowed.(Let's call them forbidden squares.) He wants to mow down the
grass on some of the squares. He must obey all these rules:
1 He can start
up at any square that can be mowed.
2 He can end up at any square that can be mowed.
3 After mowing one square he can get into one of the adjacent squares.
4 He cannot get into any of the forbidden squares.
5 He cannot get into the squares that he has already mowed.
6 If he is in some square he must mow it first. (and then decide whether to mow
the adjacent squares or not.)
7 Each square that can be mowed has a property D called beauty degree (D
is a positive integer) and if he mowed the square the beauty degree of the
meadow would increase by D.
8 Note that the beauty degree of the meadow is 0 at first.
9 Of course he cannot move out of the meadow. (Before he decided to end.)
Two
squares are adjacent if they share an edge.
Here comes the
problem. What is the maximum beauty degree of the meadow Tom can get without
breaking the rules above.

Input 
This problem has
several test cases. The first line of the input is a single integer T (1
<= T < 60) which is the number of test cases. T consecutive test
cases follow. The first line of each test case is a single line containing 2
integers N (1 <= N < 8) and M (1 <= M < 8) which is
the number of rows of the meadow and the number of columns of the meadow. Then
N lines of input describing the rows of the meadow. Each of the N
lines contains M spaceseparated integers D (0 <= D <=
60000) indicating the beauty degree of the correspoding square. For
simplicity the beauty degree of forbidden squares is 0. (And of course Tom
cannot get into them or mow them.)

Output 
For each test case output an integer in a single line which is maximum beauty degree of the meadow at last.

Sample Input 
2
1 1
10
1 2
5 0

Sample Output 
10
5

Problem Source 
ZOJ Monthly, June 2009

Submit
Discuss
Judge Status
Problems
Ranklist
