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×mn \times m grid has nn rows and mm 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 TT, meaning there will be TT independent testcases.

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

  • 1T1051 \leq T \leq 10^5

  • 1n,m1051 \leq n, m \leq 10^5

  • 4nm1054 \leq nm \leq 10^5

  • 2snm22 \leq s \leq \frac{nm}{2}

  • The sum of nmnm over all testscases 106\leq 10^6

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


For each testcase n,m,sn, m, s, output nn lines. The ii-th line will have mm contiguous characters. The jj-th character on the ii-th line should be

  • # if cell (i,j)(i,j) is an obstacle

  • s if cell (i,j)(i,j) is a start cell

  • e if cell (i,j)(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 ss. If there are multiple valid solutions, you can output any.


4 4 7
3 5 3


Login to submit.


81% Solution Ratio
niaj_pialEarliest, Feb '23
Neaj_MorshadFastest, 0.0s
CUET_WhySoSeriousLightest, 4.9 MB
EmonIIT49JUShortest, 686B
Toph uses cookies. By continuing you agree to our Cookie Policy.