| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 14 | 10 | 10 | 71.429% |
에린 대륙에는 고대 마법이 깃든 $N \times N$ 크기의 룬 격자가 존재한다. 단, 일부 칸에는 봉인된 룬이 있어 지나갈 수 없으며, $1$행, $1$열, $N$행과 $N$열에는 봉인된 룬이 없음이 보장된다.
마비노기의 고급 마법사인 밀레시안은 룬의 상태를 점검하기 위해 격자의 왼쪽 위인 $(1,1)$에서 오른쪽 아래인 $(N,N)$까지 이동한 뒤 다시 $(1,1)$로 돌아오는 왕복 경로를 설정하려 한다. 구체적으로, 밀레시안은 다음과 같은 두 경로를 따라 이동한다.
$(1,\,1)$, $(N,\,N)$을 제외한 모든 칸에서 정방향 경로와 역방향 경로는 같은 칸을 공유할 수 없으며, 격자를 위에서 아래로 보았을 때 정방향 경로는 항상 역방향 경로의 위쪽을 따라 이동한다. 따라서, 전체 왕복 경로는 시계 방향으로 이루어진다.
봉인되지 않은 모든 룬 칸은 흰색 또는 검은색의 두 상태 중 하나이다. 처음에는 모든 룬 칸이 흰색이다.
밀레시안이 어떤 칸을 한 번 지날 때마다, 해당 칸의 룬 상태는 반전된다(흰색 $\leftrightarrow$ 검은색). 단, 왕복 과정에서 $(1,1)$과 $(N,N)$은 각각 두 번 지나가는 것으로 생각하며, 이 두 칸의 룬은 항상 흰색 상태로 유지된다.
밀레시안은 가능한 서로 다른 모든 왕복 경로를 정확히 한 번씩 주행해 보았다. (정방향 경로 또는 역방향 경로에서 지나간 칸이 하나라도 다르면 서로 다른 경로로 간주한다.)
모든 왕복 경로를 주행한 뒤, 각 룬 칸의 최종 상태를 구하여라.
첫 번째 줄에 $N$이 주어진다. ($3 \leq N \leq 2 \, 000$)
두 번째 줄부터 $N$개의 줄에 걸쳐 격자의 정보가 문자열로 주어진다. .이면 봉인되지 않은 룬이 있는 칸, #이면 봉인된 룬이 있어 지나가지 못하는 칸이다.
모든 왕복 경로를 한 번씩 주행한 뒤의 격자 상태를 출력한다. 입력과 같은 형식으로 $N$개의 줄에 걸쳐 출력하며, 흰색 룬은 W, 검은색 룬은 B, 봉인된 룬은 #으로 출력한다.
$(1,1)$과 $(N,N)$은 항상 "W"를 출력함에 유의하라.
3 ... ... ...
WBW BWB WBW
가능한 모든 왕복 경로는 다음과 같다.
4 .... .... .##. ....
WBWB BBWB B##B BBBW
가능한 모든 왕복 경로는 다음과 같다.
School > 경기과학고등학교 > 나는코더다 송년대회 > 나는코더다 2025 송년대회 F번