ZOJ Problem Set - 3213
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.
Here comes the problem. What is the maximum beauty degree of the meadow Tom can get without breaking the rules above.
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 space-separated 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.)
For each test case output an integer in a single line which is maximum beauty degree of the meadow at last.
2 1 1 10 1 2 5 0
Author: CAO, Peng
Source: ZOJ Monthly, June 2009