타워 디펜스
시간 제한1초메모리 제한128 MB
격자 위 각 타워에 네 가지 직각 발사 방향 중 하나를 배정해서 동시에 발사했을 때 모든 클론을 제거하면서 다른 타워는 맞지 않도록 하는 문제입니다.
문제
회린이는 타워 디펜스 게임을 만들고 있다. 어느 날 재혁이가 개발 노트를 빼앗으려고 회사를 공격했지만, 직접 움직이기 귀찮아서 여러 클론을 만들어 침투시켰다.
회린이의 회사는 R×S 크기의 직사각형 격자이다. 격자 안에는 여러 타워가 있다. 각 타워에는 서로 직각을 이루는 대포 두 개가 달려 있으며, 한 번 발사할 때 다음 네 방향 조합 중 하나를 선택할 수 있다.
- 왼쪽과 아래쪽
- 아래쪽과 오른쪽
- 오른쪽과 위쪽
- 위쪽과 왼쪽
대포알은 발사된 방향으로 일직선으로 날아간다. 대포알이 재혁이의 클론과 부딪히면 클론만 제거되고, 대포알은 계속 같은 방향으로 날아간다. 대포알이 벽에 부딪히면 대포알만 파괴되고 벽은 그대로 남는다. 하지만 대포알이 다른 타워에 부딪히면 그 타워가 무너진다.
회린이는 모든 타워를 적절히 회전한 뒤, 모든 대포를 동시에 단 한 번 발사해서 모든 클론을 제거하려고 한다. 어떤 타워도 손상되면 안 된다. 모든 조건을 만족하도록 각 타워의 방향을 정하라.
입력
첫째 줄에 회사의 크기 R, S가 주어진다. (1 ≤ R, S ≤ 100)
다음 R개 줄에는 각 줄마다 S개의 문자가 주어지며, 회사의 지도를 나타낸다.
지도에서 대문자 T는 타워, 소문자 n은 재혁이의 클론, 문자 #은 벽, 문자 .은 빈칸을 의미한다.
항상 조건을 만족하는 답이 존재하는 입력만 주어진다. 답이 여러 개일 수도 있다.
출력
입력으로 주어진 지도에서 각 타워 칸의 T를 알맞은 숫자 1, 2, 3, 4 중 하나로 바꾸어 출력하라. 각 숫자가 나타내는 방향 조합은 문제 설명의 번호와 같다.
모든 타워의 방향을 반드시 출력해야 한다.