레이팅 미적용소 베시는 미로 풀기를 좋아한다. 또한 틱택토(정확히는 곧 설명할, 소 버전의 틱택토)도 즐겨 한다. 농부 존은 베시가 두 게임을 동시에 즐길 수 있는 새로운 방법을 찾아냈다!
먼저 소 틱택토를 설명하면, \(3 \times 3\) 격자에 X와 O를 놓는 대신, 소들은 당연히 \(3 \times 3\) 격자에 M과 O를 놓으며 게임을 한다. 자기 차례에 빈 격자 칸 아무 곳에나 'M' 또는 'O'를 놓을 수 있다 (한 플레이어는 항상 'X'만, 다른 플레이어는 항상 'O'만 놓는 표준 틱택토와의 또 다른 차이점이다). 소 틱택토의 승자는 가로, 세로, 또는 대각선으로 'MOO'를 먼저 만드는 플레이어이다. 거꾸로 만들어도 되므로, 예를 들어 한 행에 'OOM'을 만들어 이길 수도 있다. 표준 틱택토와 마찬가지로 승자가 나오지 않는 보드 상태에 도달하는 것도 가능하다. 소 틱택토의 수는 보통 'Mij' 또는 'Oij' 형태의 3개 문자로 표기하는데, 여기서 \(i\)와 \(j\)는 각각 \(1 \ldots 3\) 범위이며 해당 'M' 또는 'O'를 놓을 행과 열을 나타낸다.
베시에게 도전 과제를 주기 위해, 농부 존은 \(N \times N\)개의 칸(\(3 \leq N \leq 25\))으로 이루어진 정사각형 미로를 설계했다. 모든 테두리 칸을 포함한 일부 칸에는 커다란 건초 더미가 있어 베시가 그 칸으로 이동할 수 없다. 베시는 북, 남, 동, 서의 통상적인 4방향으로 한 칸씩 이동하며 나머지 모든 칸 사이를 자유롭게 다닐 수 있다. 일부 칸에는 소 틱택토의 수가 적힌 종이가 놓여 있다. 베시가 미로를 돌아다니다가 그런 칸을 밟을 때마다, 미로를 이동하면서 동시에 진행 중인 소 틱택토 게임에서 해당하는 수를 반드시 두어야 한다 (단, 소 틱택토 게임에서 해당 칸이 이미 차 있으면 아무 행동도 하지 않는다). 이 소 틱택토 게임에 상대는 없지만, 미로의 일부 칸은 'MOO'를 완성하려는 베시의 목표에 방해가 될 수도 있다.
베시가 이기는 즉시 소 틱택토를 중단한다고 할 때, 미로를 적절히 이동하여 만들어 낼 수 있는 서로 다른 승리 틱택토 보드 배치의 개수를 구하라.
문제 제공: Brian Dean
문제 제공: Brian Dean
입력의 첫째 줄에 \(N\)이 주어진다.
다음 \(N\)개의 줄에 각각 \(3N\)개의 문자로 미로가 주어진다. 각 칸은 3개의 문자 블록으로 표현되는데, 벽이면 '###', 빈 공간이면 '...', 베시가 있는 벽이 아닌 칸이면 'BBB', 베시가 해당 수를 두도록 강제하는 벽이 아닌 칸이면 소 틱택토의 수가 적힌다. 정확히 한 칸만 'BBB'이다.
베시가 미로에서 이동하여 (이긴 뒤에는 중단하면서) 만들어 낼 수 있는 서로 다른 승리 소 틱택토 보드 배치의 개수(0일 수도 있다)를 출력한다.
7
#####################
###O11###...###M13###
###......O22......###
###...######M22######
###BBB###M31###M11###
###...O32...M33O31###
#####################8In this example, there are 8 possible winning board configurations that Bessie
can ultimately reach:
O.M
.O.
MOM
O..
.O.
.OM
O.M
.O.
.OM
O..
.O.
MOM
O..
...
OOM
..M
.O.
OOM
...
.O.
OOM
...
...
OOM
To explain one of these, take this case:
O..
...
OOM
Here, Bessie might first visit the O11 cell, then move to the lower corridor
visiting O32, M33, and O31. The game then stops, since she has won (so for
example she would not be able to visit the M11 cell north of her current
position on the O31 cell).
riseoj 작성
출처 올림피아드 > USACO > 2020-2021 > US Open > Silver