Spawn of Ungoliant

Interview

Time limit1sMemory limit256 MB

Summary

Spiders spread to every tree connected by four-directional adjacency to an infested tree, and isolated trees and open floor stay unchanged.

Level: Easy3 of 10
Topics: BFS, Graph, Matrix
Solved: No attempts yet

Problem

The spider children of Ungoliant are spreading through Mirkwood. A giant spider cannot leave the tree it lives in, but it lays eggs in the trees next to that tree. Each egg hatches quickly and grows into another spider, which lays eggs of its own.

You are given a map of Mirkwood marking which trees hold spiders and which do not. Work out what the map looks like once the spiders have spread as far as they can.

In this problem, adjacency means one of the four cardinal directions (north, south, east, west). Two trees that touch only at a diagonal are not adjacent.

Input

The input holds several maps. The first line of a map gives the width $W$ and the height $H$ of that map. The next $H$ lines each hold a string of length $W$ describing the layout of Mirkwood. S is a tree with spiders in it, T is a tree with no spiders, and . (a period) is open forest floor with no tree.

A line where $W$ and $H$ are both 0 ends the input. Do not process that line.

Output

For each map, print the map of Mirkwood once the spiders can spread no further. Print no blank line between maps.

Examples8

Example 1

Input

3 4
T..
TST
..T
TTT
5 5
T.T.T
.T.T.
..S..
.T.T.
T.T.T
0 0

Expected output

S..
SSS
..S
SSS
T.T.T
.T.T.
..S..
.T.T.
T.T.T

Example 2

Input

2 2
S.
.T
3 3
S.T
.T.
T.S
0 0

Expected output

S.
.T
S.T
.T.
T.S

Example 3
Input
```
4 3
TTTT
TTTT
TTTT
0 0
```
Expected output
```
TTTT
TTTT
TTTT
```

Example 4

Input

6 6
STTTTT
TTTTTT
TTTTTT
TTTTTT
TTTTTT
TTTTTT
0 0

Expected output

SSSSSS
SSSSSS
SSSSSS
SSSSSS
SSSSSS
SSSSSS

Example 5

Input

8 7
STTTTTTT
.......T
TTTTTTTT
T.......
TTTTTTTT
.......T
TTTTTTTT
0 0

Expected output

SSSSSSSS
.......S
SSSSSSSS
S.......
SSSSSSSS
.......S
SSSSSSSS

Example 6

Input

7 5
TTT.TTT
TST.T.T
TTT.TTT
.......
TTTTSTT
0 0

Expected output

SSS.TTT
SSS.T.T
SSS.TTT
.......
SSSSSSS

Example 7

Input

6 1
TTSTT.
1 6
T
T
.
T
S
T
0 0

Expected output

SSSSS.
T
T
.
S
S
S

Example 8
Input
```
1 1
S
1 1
T
1 1
.
0 0
```
Expected output
```
S
T
.
```