MARIOGAM  Mario
Mario lives in an N x M maze grid. In this maze there are coin boxes, monsters, pipe systems, and walls. Whenever Mario enters a cell containing a coin box, he jumps to hit the box and gets as many coins as there are in the box (coin boxes do not disappear or lose coins after being hit). When Mario enters a cell with a monster, he loses a life. Pipe systems are like teleporters: for each system there is exactly one exit with at least one (but possibly several) entrances leading to that exit. When Mario walks into the entrance to a pipe system he is teleported to that pipe system's unique exit. Walking into a pipe system's exit does nothing special. Finally, Mario cannot walk into walls.
Mario decides to play a game. In the beginning of the game he starts with three lives at some given position, and at each time step he looks at all neighboring cells (excluding walls) and chooses one neighboring cell uniformly at random to walk to (x neighbors y if x is directly above, below, to the left, or to the right of y). If Mario has no nonwall neighboring cells then he stays at his current location. The game is over when either Mario is out of lives or it is impossible for him to collect more coins. Help Mario figure out the expected number of coins he will earn in one play of the game.
Input
The first line of the input is "N M" (1 ≤ N,M ≤ 15), giving the dimensions of the maze. What follows are N lines, each of which are M characters in length. The ith line displays the contents of the cells in the ith row of the maze. Mario starts in the unique cell with an '$' (which, beside holding Mario, is otherwise an empty cell). Cells with monsters are designated with '!'. Cells with coin boxes are represented by a number between 0 and 9 (inclusive), which is the number of coins in that coin box. Each pipe system is associated with a distinct letter between 'a' and 'z' (inclusive). A pipe system's entrances are designated with lower case letters, and the unique exit for a given pipe system has the corresponding capitalized letter (e.g. a pipe system with entrances labeled 'c' has exactly one exit, and it is labeled 'C'). Every pipe system appearing in the maze is guaranteed to have exactly one exit and at least one entrance. The character '#' designates a wall, and '.' designates an empty cell that Mario can just walk through.
Output
If the expected number of coins Mario collects is infinite, output 1. Otherwise, output a single real number, the expected number of coins Mario collects before the game is over. Your answer should be accurate to within either an absolute or relative error of 10^{6} of the actual answer. Your output should be followed by a newline.
Example
Input: 2 3 $1! a.A Output: 3.000000000
hide comments
mrmorning:
20170812 05:22:35
What is the 14th data? I've got plenty of WA from it. Annoyed. 

:D:
20120510 20:07:50
Yes, you have to think carefully about the "1" cases. I thought of quite a few issues with it, although I'm not sure how much of that is in the test cases.


Feng Yi:
20090221 07:41:07
Gaussian elimination without pretreatmengt will lead to Wrong Answer 
Added by:  Minilek 
Date:  20080110 
Time limit:  3.833s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  MIT 1st Team Contest 2007 