Raiders of the Rectangular Pool
All submissions for this problem are available.
Raiders of the Rectangular Pool.
IndianaJones (Indy), the famous archaeologist, arrived at Tunisia in search of the Lost Ark of The Covenant. While searching for the artifact in a jungle,
Indy discovers a hidden rectangular pool divided into NxM cells. In some cells of the pool there are stone islands. Each island consists of some number of
stones. Let's call this number the height of the island. Indy can jump from the island with coordinates (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 he jumps off the island its height goes down by one. If the height of any island
becomes 0 it goes underwater and he can't jump on it any more. Assume that Indy starts on an island with coordinates (sx, sy). The goal is to make all the
islands (except the final one) go underwater and finish on the island with coordinates (fx, fy) which should have height equal to 1 when you finish on it.
When this task is completed, the door to the Ark of The Covenant will open. Your task is to help Indy find the number of different ways to achieve his
The first line of input file contains number t - the number of test cases. 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.
1 0 0
3 1 1
3 1 1
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 6.3, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYPY, PYTH, PYTH 3.5, RUBY, SCALA, SCM chicken, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC|
Fetching successful submissions
If you are still having problems, see a sample solution here.