Block Drop

All submissions for this problem are available.
There is a square pool divided into NxM cells. In some cells of the pool there stone islands. Each island consists of some number of stones. Let's call this number the height of the island. You can jump from the island with coordinated (x,y) to any island with coordinates (x+1,y), (x+2,y), (x1,y), (x2,y), (x,y+1), (x,y+2), (x,y1), (x,y2). When you jump off the island its height goes down by one. If the height of any island becomes 0 it goes under water and you can't jump on it any more. You start on island with coordinates (sx, sy). The goal is to make all the islands (except the final one) go under water and finish on the island with coordinates (fx, fy) which should have height equal to 1 when you finish on it. You task is to count the number of different ways to achieve the goal.
Input
The first line of input file contains number t  the number of test cases (no more than 5 for each file). Then the description of each test case follows. The first line of each test case contains numbers N and M. The next line contains two coordinates sx and sy of the start cell. After that there are two coordinates fx and fy of the finishing cell. Then N lines follow each consisting of M integers denoting the heights of the islands in each cell of the pool. The height 0 means that there is no island in the cell. Note also that each test case in the official tests will be generated by the following procedure. The dimensions of the pool will be chosen randomly and uniformly: N and M will be from 3 to 8 inclusive. Then the final cell will be chosen randomly: fx will be from 1 to N and fy will be from 1 to M. The height of island in the cell (fx, fy) will be set to 1. Then the number of jumps will chosen randomly from 15 to 25. Then this many random valid jumps will be performed adding one stone to the cell the jumps lands on. The cell on which we land after performing all the jumps will be proclaimed as the initial cell: (sx, sy).
Output
For each test case print the total number of different ways to solve the task.
Example
Input: 1 3 3 3 1 3 1 1 0 0 3 1 1 3 1 1 Output: 152
Author:  spooky 
Tester:  gamabunta 
Editorial  http://discuss.codechef.com/problems/BLOCKDRO 
Tags  aug11, medium, spooky 
Date Added:  9072011 
Time Limit:  0.95092 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, 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
HELP
If you are still having problems, see a sample solution here. 