Block Drop

Problem code: BLOCKDRO

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), (x-1,y), (x-2,y), (x,y+1), (x,y+2), (x,y-1), (x,y-2). 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
Date Added: 9-07-2011
Time Limit: 5 sec
Source Limit: 50000 Bytes
Languages: ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC


Comments

where is the origin?

tru3liar @ 16 Oct 2011 01:21 PM
where is the origin?

Does the time limit of 5

harithag0_0 @ 27 Jan 2012 11:03 AM
Does the time limit of 5 seconds imply that each test input file be solved with in 5 seconds or all the test input files be solved in 5 seconds. Will u test this program on one test file with multiple test cases or many such test files?

Please explain in details on

rakesh_software206 @ 27 Feb 2012 02:39 PM
Please explain in details on these line. 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). It's confusing me.

First, the origin should be

jackhftang @ 22 Apr 2012 01:19 PM
First, the origin should be stated clearly. Second, as far as I understand, the sum of height of all island should be equal to the number of jump, which should be between 15 to 25 as implied in description. However, in the example, the sum is 11, which should not be that.

logical conclusion makes me

wtq4er @ 15 May 2012 06:38 AM
logical conclusion makes me think that in example coordinates (3,1) is the lower left corner. So this means that in all test cases we have the coordinate system with X axis directed downstairs and Y axis directed rightward. admin, Is this correct? Or may be it is better to think of coordinates as the number of row and the number of column...

@rakesh_software206 This part

arpit_agrwl @ 21 May 2012 09:42 AM
@rakesh_software206 This part explains how exactly the program is generating the input file which contains the Heights of the islands. 1.It randomly chooses a finishing cell. 2.A number between 15-25 is chosen. 3.It randomly starts jumping to the possible cells and increases the height of the island it jumps on and continues till the number of jumps which were randomly selected (15-25) are exhausted. 4.Thus we get the initial cell. The program is going in a reverse manner to generate the input file.

@jackhftang I think you are

arpit_agrwl @ 21 May 2012 09:46 AM
@jackhftang I think you are right. ADMIN PLEASE HELP

what if no jumps are

saurabharaiyer @ 21 May 2012 11:29 AM
what if no jumps are possible?

SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:

HELP

Program should read from standard input and write to standard output. After you submit a solution you can see your results by clicking on the [My Submissions] tab on the problem page. Below are the possible results:

 

  • Accepted Your program ran successfully and gave a correct answer. If there is a score for the problem, this will be displayed in parenthesis next to the checkmark.
  • Time Limit Exceeded Your program was compiled successfully, but it didn't stop before time limit. Try optimizing your approach.
  • Wrong Answer Your program compiled and ran succesfully but the output did not match the expected output.
  • Runtime Error Your code compiled and ran but encountered an error. The most common reasons are using too much memory or dividing by zero. For the specific error codes see the help section.
  • Compilation Error Your code was unable to compile. When you see this icon, click on it for more information.

    • If you are still having problems, see a sample solution here.

CodeChef is a global programming communityCodeChef hosts online programming competitions