P2407 [SDOI2009] Map Restoration

Long ago, there was a legendary tribe called "EWF" who lived on an $N \times M$ rectangular land. Although there were mountains and swamps, through hard work and courage, they eventually built a loop on their territory. Later, the "EWF" tribe mysteriously disappeared. However, archaeologists found a map in the place where they once lived. The map is an $N \times M$ matrix, with the top-left coordinate at $(0, 0)$ and the bottom-right coordinate at $(N, M)$. Each cell represents one of the following: mountain, swamp, plain, house, or road. If a cell represents a road, then the road passing through this cell is either straight or turning. As shown below, the two on the left are straight cells, and the four on the right are turning cells. A cell that represents a road can only be one of the cases below.  However, due to the age of the map, while archaeologists can identify the type of terrain each cell represents, for road markings they can only distinguish whether a cell is straight or turning. Now they ask for your help to restore the "EWF" tribe’s map.

The first line of the input file recover.in contains two positive integers $N$ and $M$ separated by a space, representing the height and width of the map. Then follows an $N$-row, $M$-column matrix describing the map, with no extra characters. Uppercase "S" denotes a straight road cell, uppercase "T" denotes a turning road cell, and "." denotes mountain, swamp, plain, or house.

The output file recover.out contains $2N - 1$ lines, each with $2M - 1$ characters, describing the loop. For all positions at row $2i + 1$, column $2j + 1$, the character is the lowercase letter "o", representing the center $(i, j)$ of the cell in row $i$, column $j$ of the matrix. If the loop contains a path from $(i, j)$ to $(i, j + 1)$ or from $(i, j + 1)$ to $(i, j)$, then the character at row $2i + 1$, column $2j + 2$ is a hyphen "-" (ASCII code 45). If the loop contains a path from $(i, j)$ to $(i + 1, j)$ or from $(i + 1, j)$ to $(i, j)$, then the character at row $2i + 2$, column $2j + 1$ is a vertical bar "|" (ASCII code 124). All other positions not mentioned above are spaces (ASCII code 32). The input guarantees that there exists at least one valid solution, so your output should contain exactly one loop. If multiple answers exist, output any one of them.

- For 20% of the testdata, $N \le 10$. - For 40% of the testdata, $1 \le N, M \le 80$. - For 40% of the testdata, the input contains no ".", and $N, M > 10$. - For 100% of the testdata, $1 \le N, M \le 800$. Translated by ChatGPT 5