Limits
1s, 512 MB

Mr O is teaching Algorithms 101 to his students. The class just finished learning BFS and now he wants to test their understanding. So he came up with the idea of telling them to solve the shortest path problem in a grid. In particular, A $n \times m$ grid has $n$ rows and $m$ columns and Mr O has marked some grid cells as "obstacles". His students have to find the shortest distance from a "start" cell to an "end" cell. From a cell one can go left, right, up or down provided one does not go outside the grid and the cell they go to is not an obstacle. Mr O will assign two distinct non-obstacle cells as start and end.

Quite happy with himself, he realized that now he has to make testing data to test his students. In other words, he needs to come up with some grids with a known shortest distance between the start and end cell (The length of a path through the grid is the number of cells on the path). Being a bit lazy, Mr O has hired you to construct such grids. He will tell you the grid dimensions and the required shortest distance, you just need to construct the grid. **Note** that the shortest distance means the count of cells in the shortest path, including the start and end cells.

The first line will contain a positive integer $T$, meaning there will be $T$ independent testcases.

Then there will be $T$ lines, The $i$-th line will contain 3 integers $n, m, s$ meaning you have to create a $n \times m$ grid where the shortest distance between start and end cell is exactly $s$.

$1 \leq T \leq 10^5$

$1 \leq n, m \leq 10^5$

$4 \leq nm \leq 10^5$

$2 \leq s \leq \frac{nm}{2}$

The sum of $nm$ over all testscases $\leq 10^6$

Under these constraints, it is always possible to create a required grid.

For each testcase $n, m, s$, output $n$ lines. The $i$-th line will have $m$ contiguous characters. The $j$-th character on the $i$-th line should be

`#`

if cell $(i,j)$ is an obstacle`s`

if cell $(i,j)$ is a start cell`e`

if cell $(i,j)$ is an end cell`.`

otherwise

Note your output must have exactly one start cell and one end cell. There are no constraints on the number of obstacles or free cells. The shortest distance between the start and end cell must be exactly $s$. If there are multiple valid solutions, you can output any.

Input | Output |
---|---|

2 4 4 7 3 5 3 | s... .##. .##. ...e .s.e. ..... ..... |

Login to submit.

77%
Solution Ratio

niaj_pialEarliest,

Neaj_MorshadFastest, 0.0s

HSTU_TREENITYLightest, 4.9 MB

EmonIIT49JUShortest, 686B

Toph uses cookies. By continuing you agree to our Cookie Policy.