Little Elephant and Mouses

All submissions for this problem are available.
It is wellknown that the elephants are afraid of mouses. The Little Elephant from the Zoo of Lviv is not an exception.
The Little Elephant is on a board A of n rows and m columns (0based numeration). At the beginning he is in cell with coordinates (0; 0) and he wants to go to cell with coordinates (n1; m1). From cell (x; y) Little Elephant can go either to (x+1; y) or (x; y+1).
Each cell of the board contains either 1 or 0. If A[i][j] = 1, then there is a single mouse in cell (i; j). Mouse at cell (i; j) scared Little Elephants if and only if during the path there was at least one such cell (x; y) (which belongs to that path) and ix + jy <= 1.
Little Elephant wants to find some correct path from (0; 0) to (n1; m1) such that the number of mouses that have scared the Little Elephant is minimal possible. Print that number.
Input
First line contains single integer T  the number of test cases. Then T test cases follow. First line of each test case contain pair of integers n and m  the size of the board. Next n lines contain n strings, each of size m and consisted of digits 0 and 1.
Output
In T lines print T integer  the answers for the corresponding test.
Constraints
1 <= T <= 50
2 <= n, m <= 100
Example
Input: 2 3 9 001000001 111111010 100100100 7 9 010101110 110110111 010011111 100100000 000010100 011011000 000100101 Output: 9 10
Explanation
Example case 1:
The optimized path is: (0, 0) > (0, 1) > (0, 2) > (0, 3) > (0, 4) > (0, 5) > (0, 6) > (0, 7) > (0, 8) > (1, 8) > (2, 8). The mouses that scared the Little Elephant are at the following cells: (1, 0), (1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 7), (0, 2), (0, 8).
Example case 2:
The optimized path is: (0, 0) > (1, 0) > (1, 1) > (2, 1) > (2, 2) > (3, 2) > (3, 3) > (4, 3) > (4, 4) > (5, 4) > (5, 5) > (6, 5) > (6, 6) > (6, 7) > (6, 8). The 10 mouses that scared the Little Elephant are at the following cells: (0, 1), (1, 0), (1, 1), (2, 1), (3, 3), (4, 4), (5, 4), (5, 5), (6, 6), (6, 8).
Author:  witua 
Tester:  tuananh93 
Editorial  http://discuss.codechef.com/problems/LEMOUSE 
Tags  dynamicprogramming, easymedium, june13, witua 
Date Added:  20032012 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions