인간의 실수

Justin과 Donald는 그들이 가장 좋아하는 게임인 홉 체스를 한다. 아마 들어본 적은 없겠지만, 규칙은 꽤 간단하다.

보드는 직사각형 격자이고, 각 칸에는 처음에 정확히 한 명의 말이 놓여 있다. Justin의 말은 J, Donald의 말은 D로 표시한다. 처음에 각 플레이어는 보드 위에 적어도 하나의 말을 가지고 있다.

게임은 Justin이 먼저 두면서 시작한다. 자기 차례에 플레이어는 자신의 말 하나를 인접한 말로 옮겨 잡을 수 있다(그리고 그 말을 보드에서 제거할 수 있다). 인접한 말은 반드시 상대방의 말일 필요는 없다. 말 X가 Y의 위, 아래, 왼쪽, 오른쪽 중 한 곳에 있으면 X가 Y에 인접하다고 한다. 이런 수를 둘 수 없으면, 차례인 플레이어가 진다.

이상적인 세상에서는 Justin과 Donald 모두 완벽한 논리학자이고, 어떤 보드에 대해서든 최적의 전략을 알아낼 수 있다. 그러면 우리는 둘 중 누가 이길지에 관심이 있을 것이다. 하지만 그렇게 현실적이지는 않다. 실제로 게임을 할 때 Justin과 Donald는 둘 다 비교적 좋은 해답을 떠올릴 수 있는데, 그것이 얼마나 좋은지는 각자의 오류 계수 J와 D로 결정된다.

형식적으로, 오류 계수가 A인 차례의 플레이어는 먼저 제안 집합을 고른다. 가능한 수가 A개 이하이면 가능한 모든 수의 집합을, A개보다 많으면 가능한 수의 집합에서 크기 A인 부분집합을 고른다. 그런 다음 이 제안 집합에서 수 하나를 같은 확률로 무작위로 선택한다.

두 플레이어는 제안 집합을 고를 기회가 주어지면 가장 최적인 집합(이길 확률이 가장 높은 집합)을 고르며, 상대방도 항상 제안 집합을 최적으로 고른다는 것을 알고 있다.

그러면 자연스러운 질문은 이것이다. 초기 보드와 J, D가 주어졌을 때 Justin이 홉 체스 게임에서 이길 확률은 정확히 얼마인가?

입력은 두 개의 공백으로 구분된 양의 정수 R, C(R · C ≤ 13)로 시작한다. 다음 R개 줄에는 {J, D}의 문자로 이루어진 길이 C의 문자열이 주어지며, 초기 보드 상태를 나타낸다. 마지막으로 두 개의 공백으로 구분된 정수 J, D(1 ≤ J, D ≤ 13)가 주어진다.

Justin이 이길 확률을 소수점 셋째 자리에서 반올림하여 하나의 부동 소수점 수로 출력한다.