웅골리안트의 자손
면접 대비시간 제한1초메모리 제한256 MB
거미가 든 나무와 상하좌우로 이어진 모든 나무에 거미가 번진 뒤 지도를 그대로 출력합니다.
문제
웅골리안트의 자손인 거미들이 어둠숲으로 퍼지고 있다. 거대 거미는 자기가 자리 잡은 나무를 떠나지 못하지만, 바로 옆 나무에 알을 낳는다. 알은 금방 부화해 새 거미가 되고, 그 거미가 다시 옆 나무에 알을 낳는다.
거미가 사는 나무와 거미가 없는 나무가 표시된 어둠숲 지도가 주어진다. 거미가 더 퍼질 수 없을 때까지 퍼지고 난 뒤의 지도를 구하라.
이 문제에서 인접은 동서남북 네 방향만 뜻한다. 대각선으로 맞닿은 두 나무는 인접하지 않는다.
입력
입력은 지도 여러 개로 이루어진다. 각 지도의 첫 줄에는 지도의 너비 와 높이 가 주어진다. 이어지는 개의 줄에는 길이가 인 문자열이 주어져 어둠숲의 배치를 나타낸다. S는 거미가 사는 나무, T는 거미가 없는 나무, .(마침표)는 나무가 없는 숲 바닥이다.
와 가 모두 0인 줄이 나오면 입력이 끝난다. 이 줄은 처리하지 않는다.
출력
지도마다 거미가 더 퍼질 수 없게 된 뒤의 어둠숲 지도를 출력한다. 지도와 지도 사이에 빈 줄을 넣지 않는다.