BLOCKDRO - Block Drop

no tags 

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.


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).


For each test case print the total number of different ways to solve the task.


3 3
3 1
3 1
1 0 0
3 1 1
3 1 1


hide comments
shihanyuan: 2012-06-05 01:25:29

what's the answer for this test:

8 8
4 1
5 3
0 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0
1 0 0 0 0 0 0 0
2 1 0 0 0 0 0 0
3 1 3 1 0 0 0 0
3 3 1 0 0 0 0 0
1 1 1 0 0 0 0 0
1 1 0 0 0 0 0 0

[Rampage] Blue.Mary: 2011-08-31 07:36:32

Another constant optimization problem. (I've only used the data limits in the random generation procedure...)

Last edit: 2011-08-31 07:53:40
:D: 2011-08-31 05:53:53

The random generation procedure specified in description is important. It is required to do certain optimizations that will be effective for this particular class of test cases.

:D: 2011-08-26 08:34:02

Nice problem. Also look for a flash game named "Block Drop" for visualization :)

Added by:Spooky
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:CodeChef August 2011 Long Contest