three pigs

Three Pigs


One day three pigs decide to go to their friend - Patachok. As their custom they want to give a present to Patachok. Because they live in forest, three pigs decide to take as much acorns as they can on their way to Patachok. But a wicked wolf finds out the pigs' plan. So the wolf puts traps on the pigs' way. You are asked to help the pigs. Note that the forest is a square (MxM, 1<=M<=11). Pigs' house is the leftmost and uppermost cell, Patachok's house in the rightmost and bottom most cell. "0" means that there is nothing in the cell, "1" means that there is one acorn in the cell, "2" means that there is a trap in the cell. Pig can go from one cell to other if they have a common side. A pig can't "visit" the same cell twice. Path of different pigs can be different. Any path begins in cell (1, 1) and ends in cell (N, N).

Input:


The first line of input contains a single number N - number of test. The next lines are tests. The first line of each test contains a single number M. The next M lines each contains M numbers (the number found on the j-th position on the i-th line represent a cell (i, j)).




Output:


You should output a single number on a single line for each test - the maximum possible amount of acorns or "-1" (without the quote) if the wolf catch the pigs.




Sample Input:


2


3


0 0 1


0 1 0


0 2 0


4


0 0 0 0


2 1 0 0


2 1 2 0


2 1 2 0



Sample Output:


2


1

CAN ANYONE HELP ME TO SOLVE THIS PROBLEM OR MAKE AN ALGORITHM OR AT LEAST GIVE ME SOME REFERRENCE??

Hmm, I think an algorithm would start off by blocking off dead ends and numbering the non dead-ended acorns (to save running time) and then finding all paths from start to end, keeping track of which acorns each path gets, exiting if a path is found which gets all the possible acorns. If no paths get to Patachock it's easy, if some paths work but non get all the acorns then you have to categorise them according to which acorns they collect, and find the combination of up to three categories that gets the most different acorns. For neatness you could build up the categories piece by piece as you find the paths.

first: this post is bs, i have no real idea what i am talking about. i cant even spell properly.

iamatiger is right about identifing which acorns can be reached at all, but i note that as no pig can land on the same cell twice, and they can only move to ajacent cells, an acorn only needs to be boxed on three sides to make it unreachable, two if it is on a side, and one if it is in a corrner.
the next step depends on the power of your computer (and on M)
if you can:
identify every possible path, and every possible set of three paths, and eliminate all sets that do not include all the acorns. then take the set with the shortest sum of lengths of paths.

if you want to save cpu:
preprogram in everything easy. the solutions for every possible set up with m<4 should be figurable.
then, if 3<M<8:
*find all the possible paths, and take the five that catch the most acorns, then listh the 125 possible sets of three, and check that at least 30 catch all acorns.
if yes: of those 30+, take the shortest.
if no: repeat from the astrix, execpt take one more than last time (instead of "...the five that...", "...the six that..." )
if M>8, then divide the feild into sections with horrisontal or vertical lines, each thourgh the entire feild, between cells, use (M-9) more than the fewest such lines nessesary to place each acorn in it's own section.
treat each section as a cell and repeat from the top.
then, within each section, solve that section as if it were a compleat feild, changing the rules for this step only in that the feild may not be square, and all that matters is that the pig gets the acorn, it starts on the correct side, and it ends on the correct side. if two pigs cross the same section, then figure both and take the shorter.

this is not garenteed to give you the best answer, but it should give you a good answer every time.

it occored to me that you could shorten your path/sets even more if you did one pig, eliminated the acorns he picked up, then did the next pig, except that i dont know how to determin how many acorns the first pig should be required to get, and that is importnat.

anyway, my attention span is running out, i have to bike home, and it's getting colder out by the minute.

all these numbers are arbitrary, i choose them because they seemed about right.