파친코
면접 대비시간 제한1초메모리 제한1024 MB
장애물과 숫자 게이트가 있는 격자에서 공을 한 열에 떨어뜨릴 때, 장애물마다 50대 50으로 갈라지며 내려가 얻는 기대 상금의 최댓값을 구한다.
문제
파친코는 오락과 상품을 위해 즐기는 일본의 게임으로, 핀볼과 비슷하다. 규칙은 아주 단순하다. 작은 쇠공을 기계 안으로 쏘아 넣으면 공이 떨어지면서 장애물에 부딪혀 튕기다가 어느 게이트로 떨어진다. 공이 들어간 게이트가 상금을 결정한다.
공을 어느 열에 떨어뜨릴지는 어느 정도 정할 수 있으므로(초기 속도와 방향을 조절해서) 당첨 확률에 영향을 줄 수 있다. 당신은 기대 상금을 계산해야 한다.
파친코 기계는 다음과 같이 모델링한다. 공을 아무 열에나 떨어뜨릴 수 있고, 공은 기계의 바닥에 닿거나(당첨 없음), 게이트(1부터 9까지의 숫자로 표시되며, 그 숫자만큼 당첨) 또는 장애물(별표로 표시)에 닿을 때까지 아래로 떨어진다. 공이 장애물에 닿으면 장애물의 왼쪽 또는 오른쪽 열로 떨어지며, 확률은 각각 50%다. 어떤 두 장애물이나 게이트도 인접하지 않으며, 대각선으로도 인접하지 않고, 어느 것도 가장 왼쪽이나 가장 오른쪽 열에 있지 않다.
입력
첫 줄에 정수 t (1 ≤ t ≤ 100)가 주어진다. 이는 테스트 케이스의 수다. 각 테스트 케이스는 다음과 같다.
- 두 정수 h와 w (1 ≤ h, w ≤ 100)가 주어지는 한 줄. 파친코 기계의 높이와 너비다.
- 파친코 기계를 나타내는 w개의 문자로 이루어진 h개의 줄. ‘
.’은 빈 공간, ‘*’는 장애물, ‘1’. . . ‘9’는 당첨 게이트다.
출력
각 테스트 케이스마다:
- 최대 기대 상금을 한 줄에 출력한다. 절대 오차 또는 상대 오차가 10−6 이하여야 한다.