Archibald and Adalbert are inseparable friends and the best knights of the whole kingdom. Com-
petitive as they are, they occasionally engage in a little open-air sword fight, just to determine who
among them really is the first knight. Of course, neither Adalbert nor Archibald wins, but they keep
themselves busy for quite a while and get around in the surroundings. You have to calculate about
how long their next ‘fight’ will last.
All the action takes place in a rectangular area which, for the sake of simplicity, is divided into unit
squares numbered from (1, 1) to (m, n). Starting at (1, 1), the knights move from one square to one of
the at most four adjacent squares, and finish as soon as they reach (m, n) where the tavern is located.
At each square, it is largely a matter of chance where the fight will continue, but it also depends
on the environment (for example, if a certain direction is uphill). Our model uses probabilities to
decide into which adjacent square the fight will move next. (For example, an uphill direction has a
lower probability.) It is your job to calculate the expected number of moves that are needed before
the tavern is reached. You can assume that every move is independent of the directions chosen in
the previous moves.
The input consists of a sequence of rectangular areas. Each area starts with a line containing the
dimensions of the rectangle m and n, where 1 ≤ m, n ≤ 40. Four blocks follow that state the
probability of a move in each direction. Every block contains m lines, and each line contains n
numbers pi,j(k) , where 0 ≤ pi,j(k) ≤ 1 for all 1 ≤ i ≤ m and 1 ≤ j ≤ n and 1 ≤ k ≤ 4. The probabilities
in block k are arranged as follows:
(k) (k) (k) (k) (k)
p1,1 p1,2 p1,3 ... p1,n−1 p1,n
(k) (k) (k) (k) (k)
p2,1 p2,2 p2,3 ... p2,n−1 p2,n
.
.
.
(k) (k) (k) (k) (k)
pm,1 pm,2 pm,3 ... pm,n−1 pm,n
For each area, output a line containing the expected number of moves from (1, 1) to (m, n). This
number must be rounded off to 6 digits after decimal the exact answer that is always less than 5000000.
2 2 0.01 0.50 0.00 0.00 0.99 0.00 0.50 0.00 0.00 0.00 0.50 0.00 0.00 0.50 0.00 0.00 1 5 0.0 0.0 0.0 0.0 0.0 1.0 0.1 0.7 0.5 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.9 0.3 0.5 0.0 3 3 0.000001 0.0 1.0 0.0 1.0 1.0 0.0 0.0 0.0 0.999999 1.0 0.0 1.0 0.0 0.0 0.000001 0.000001 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.999999 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.999999 0.0 0 0
4.000000 41.142857 7.999994
Migrated from old NTUJ.
SWERC 2008
| No. | Testdata Range | Score |
|---|