Rotating Maze
Пролетен Турнир по Информатика, 2015
Time Limit: 0.4s, Memory Limit: 64MiB
Ели се намира в лабиринт с N реда и M колони, като в началото е в най-горната лява клетка, а изходът се намира в най-долната дясна. За да стигне до изхода, Ели е решила да използва единствено движения надолу и надясно.

Всяка клетка от лабиринта представлява мост, които може да бъде хоризонтален ('-'), вертикален ('|') или "кръстовище" ('+'). От хоризонтален мост може да се премине в друг хоризонтален или в кръстовище на същия ред. От вертикален може да се премине в друг вертикален или в кръстовище на същата колона. От кръстовище може да се премине във вертикален (отдолу), в хоризонтален (отдясно), или в друго кръстовище (отдолу или отдясно).

Всяка минута всеки мост (включително този, на който се намира момичето) има шанс 50% да се завърти на 90 градуса. Тоест '-' става '|' с шанс ½ или остава '-' с шанс ½. Обратно, '|' става '-' с шанс ½ или остава '|' с шанс ½. Независимо дали се завъртят или не, кръстовищата '+' си остават '+'.

Момичето може да премине от един мост на съседен такъв за една минута. Така, започвайки от първата минута, на всяка минута момичето преминава в клетката надолу или надясно, или стои на сегашната си позиция, ако не може да продължи в никоя от двете посоки. Ако пък може да продължи и в двете, тя избира една от тях на произволен принцип. Ели не може да излиза извън лабиринта.

Редът на събитията всяка минута е:
  1. Първо някои (потенциално всички или никой) от мостовете се завъртат;
  2. След това Ели решава на къде да се придвижи (и го прави, ако има накъде).

Сега момичето се чуди за колко време ще излезе от лабиринта. Помогнете й, като напишете програма, която намира очаквания брой минути за достигане на долната дясна клетка.
Вход
На първия ред на стандартния вход ще бъдат зададени целите числа N и M - съответно броя редове и колони на лабиринта. Следват N реда с по M символа от азбуката {'-', '|', '+'} - описанието на първоначалното състояние на мостовете в клетките на лабиринта.
Изход
На единствен ред на стандартния изход изведете очаквания брой минути за достигане до крайната клетка. Отговорът ще бъде зачетен за верен при абсолютна или релативна разлика, по-малка от 10-9.
Ограничения
  • 1 ≤ N, M ≤ 1,000
  • Или N или M ще бъде по-голямо от едно.
Примерен Вход Примерен Изход
1 3 -+| 4.0
2 3 -+| ++- 4.25
13 11 -+-+||-+++- ++|+-|--|++ +--+-|-++++ ||+-+-||++| +-+-+||--+- +--||-|+-|- |+++++-+-+- ||-||--+||- |+|-+-+|-|- +-+++|--||+ +|||--+||-+ +|++|+||+-| ++-+-+|--|| 36.347956
В първия пример на първата минута в зависимост дали мостът в (1, 1) се е завъртял или не Ели може да премине в клетката (1, 2) с шанс ½ или остава в същата клетка също с шанс ½. Ако мостът се е завъртял (тоест е станал '|') тя трябва да изчака 1 или повече минути, докато стане отново '-'. Може да се покаже, че очакваното време за преминаването на момичето в съседната клетка е 2 минути (1/2 * 1 + 1/4 * 2 + 1/8 * 3 + 1/16 * 4 ... = 2). След като е стигнала до клетката (1, 2) тя е в сходна ситуация – клетката (1, 3) може да е '|', в който случай тя трябва да изчака докато стане '-'. Очакваното време за това отново е 2, което прави очакваното време за преминаване на целия лабиринт 4 минути.

Във втория пример момичето има възможност да отиде и надолу. Ако мостът в (1, 1) е станал '|', момичето отива в (2, 1) за 1 минута, след това в (2, 2) за още една и накрая в (2, 3) за две – тоест очакваното време ако мостът в (1, 1) е '|' е 4 минути. В противен случай момичето отива в (1, 2) в първата минута.След това с шанс ½ мостът в (1, 3) се завърта към нея (тоест става '-'), в който случай тя има избор между това да отиде надолу или надясно. Ако пък мостът не сочи към нея, момичето слиза надолу в (2, 2). Тоест, във втората минута момичето с шанс ¼ отива в (1, 3) и с ¾ в (2, 2). Ако се намира в (1, 3) момичето трябва да изчака докато мостовете в (1, 3) и (2, 3) едновременно станат '|'. Очакваното време за това е 1/4 * 1 + 3/16 * 2 + 9/64 * 3 +... = 4, така че ако е минала през (1, 3) Ели би излязла от лабиринта за 6 минути (1 + 1 + 4). Ако се намира в (2, 2) момичето трябва да изчака докато мостът в (2, 3) се завърти към нея. Както видяхме в първия пример, очакваното време това да се случи е 2 минути, съответно момичето би излязло от лабиринта за 4 минути (1 + 1 + 2). Тоест, ако Ели се озове в (1, 2), очакваното време за преминаване на лабиринта е ¾ * 4 + ¼ * 6 = 4.5 минути. Така можем да сметнем и очакваното време за целия лабиринт: ½ * 4 + ½ * 4.5 = 4.25 минути.
Мрън!