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
Tester: gamabunta
Editorial http://discuss.codechef.com/problems/BLOCKDRO
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, FORT, FS, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, 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

What is happening with the

khaustov @ 1 Aug 2011 04:01 PM
What is happening with the statement? What size does the pool have: "N x M" or "N x N"? "Input" and "Example" are contradictory.

There is an error in the

neil_mahaseth @ 1 Aug 2011 04:11 PM
There is an error in the input statement it says "The first line of each test case contains number N" .It should be"The first line of each test case contains numbers N and M". Then "Then N lines follow each consisting of N integers denoting the heights of the islands in each cell of the pool." should be"Then N*M lines follow each consisting of N*M integers denoting the heights of the islands in each cell of the pool."

Wrong again? May be like this

khaustov @ 1 Aug 2011 04:14 PM
Wrong again? May be like this "Then N lines follow each consisting of M integers..."?

No allowed programming

khaustov @ 1 Aug 2011 04:35 PM
No allowed programming languages! What's happening?! I can't submit!

Sorry for the inconvenience!

shilp_adm @ 1 Aug 2011 04:42 PM
Sorry for the inconvenience! Looking into this immediately!

This is fixed. Sorry for the

shilp_adm @ 1 Aug 2011 04:52 PM
This is fixed. Sorry for the inconvenience.

"Then the number of jumps

vaibhav6980 @ 1 Aug 2011 05:53 PM
"Then the number of jumps will chosen randomly from 15 to 25." Please explain this statement it is confusing.

It describes how the input is

shilp_adm @ 1 Aug 2011 05:57 PM
It describes how the input is being generated (so you know what to expect in the judge input). Each case is generated such that the number of jumps that solves the case is between 15 and 25.

is the initial cell to be

feluda @ 1 Aug 2011 07:00 PM
is the initial cell to be zero

@feluda if you mean whether

shilp_adm @ 1 Aug 2011 07:22 PM
@feluda if you mean whether the number of stones at the initial position be zero, then no. it won't be. you can derive so from the problem statement!

Please clarify .. 1 3 3 3 1 3

maverick_dp @ 1 Aug 2011 11:20 PM
Please clarify .. 1 3 3 3 1 3 1 1 0 0 3 1 1 3 1 1 if (3,1) height is only one and it is start and finish. A single jump will make the end point to have 0 height. In the input 1 0 0 3 1 1 3 1 1 where is the origin located??

or to be more simple what is

maverick_dp @ 1 Aug 2011 11:22 PM
or to be more simple what is the value(no of stones) of the co-ordinate 3,1 in the above test case..

@maverick_dp I believe you

shilp_adm @ 2 Aug 2011 03:48 AM
@maverick_dp I believe you are confusing (x, y) with the x / y - axes. Please consider (x, y) to be the co-ordinate at the x'th row and y'th column! So number if stones at (3, 1) in the above case is 3.

taking bottom-left corner to

abhishek308 @ 2 Aug 2011 10:58 PM
taking bottom-left corner to be origin. Isn't number of stones at (3,1) one(1). Also, it clearly states in the question that. height (Fx,Fy) already set to 1. But the problem is since Sx,Sy is also (3,1). Wouldn't it make it 0 on the first jump.

@abhishek308 origin is at

shilp_adm @ 3 Aug 2011 01:10 PM
@abhishek308 origin is at top-left. the number of stones at (3,1) are 3.

This has to be the worst

pr0ton @ 4 Aug 2011 03:19 AM
This has to be the worst problem ever set in a monthly. There is no sense in setting a problem, which ONLY requires optimizations to a naive solution without any new ideas. Just totally pathetic.

It is said "Then the number

ishandutta2007 @ 4 Aug 2011 08:28 AM
It is said "Then the number of jumps will chosen randomly from 15 to 25";but for the given example it can be reached in 10 jumps.Isn't it?

@pr0ton probably your

gultus @ 4 Aug 2011 09:32 AM
@pr0ton probably your definition of naive and my definition differ as I don't see any possible optimizations for my naive solution so that it doesn't get TLEd. Let me give it a couple of more attempts and not give up yet.

@Proton , many a times ,

mkagenius @ 4 Aug 2011 12:29 PM
@Proton , many a times , there exists a good solution which gets AC and there exists a naive one , which gets AC on lots of optimization( which the author did not want), but thats the way it goes.

@admin Whtz the time limit of

linkin @ 4 Aug 2011 02:14 PM
@admin Whtz the time limit of this problem? It is given 5s...bt how most of the people got AC in 10s ?

@linkin Please read the FAQ

balajiganapath @ 4 Aug 2011 03:48 PM
@linkin Please read the FAQ

Just wondering, is there any

mmaxio @ 5 Aug 2011 06:57 AM
Just wondering, is there any accepted solution in Java? Or maybe problem setters have one?

There is an accepted solution

shilp_adm @ 5 Aug 2011 04:48 PM
There is an accepted solution in Java.

hey admin, Im getting a

r_ninja07 @ 6 Aug 2011 05:45 PM
hey admin, Im getting a runtime error on running my code, how can I find out where's the error coming from? its java 1.6.0_26, compiles in NetBeans 7.0

n by the way.. I think the

r_ninja07 @ 6 Aug 2011 06:14 PM
n by the way.. I think the answer to above example should be 153.. I mean thats what I got.

My code gives me 152 so +1

gultus @ 6 Aug 2011 09:46 PM
My code gives me 152 so +1 vote to the sample test case from my side. But that can't be conclusive enough as my code is getting TLEd.

@Shilp i m getting answers

rachit001 @ 7 Aug 2011 11:51 PM
@Shilp i m getting answers correctly... i hav even tested test case.. i gives right output.. i hav reduced the complexity of the porgram... but it's still showing time limit exceeded... enlighten me... :)

@proton any help on above

rachit001 @ 11 Aug 2011 03:24 PM
@proton any help on above comment... i use recursion in my program..... wat shuld i do?

SUCCESSFUL SUBMISSIONS


Fetching successful submissions