ParkPlace

There is a square-shaped park which is subdivided into N * N unit square cells.

The edges of the park are going in the north-south and east-west directions. We will assign two coordinates (row, column) to each cell in such a way that row numbers grow from the north to the south and column numbers grow from the west to the east.

You are given the String[] place that describes the layout of the park. More precisely, the character place[r][c] describes the cell (r, c). In this park, each cell is either a tree (denoted '#') or grass (denoted '.').

We would like to make our park more attractive to visitors by building walkways. The walkways must be built according to the following rules:

• A walkway cannot enter a tree cell.
• Each grass cell must be crossed by exactly one walkway.
• For each grass cell, the walkway must enter the cell through one edge (not through a corner) and leave the cell through some other edge.
• Walkways cannot cross the boundary of the park.

Note that the above rules imply that in any valid layout of the park the walkways will form a collection of disjoint cycles that, taken together, cover all the grass cells.

Write a program to find if it is possible to design such a collection of walkways. If it is, construct any one such layout and return its description. The way to return the answer is as follows:

• If it's not possible to place the walkways according to the rules, return an empty String[].
• If there's at least one valid solution, choose any one such solution. Then, return a String[] with length equal to the number of cycles your walkways form. Each element of the return value will describe one of these cycles. More precisely:
  • Each element should have the form "R C movements".
  • "R" and "C" should be the coordinates (row, column) of any one cell on the walkway.
  • Finally, "movements" should be a string in which each character is 'N', 'E', 'S', or 'W'. This string represents a sequence of movements that will walk along the cycle, visiting each cell once and then ending in the cell (R, C) where you started.
  For example, "5 8 NNEESWSW" represents the 8-cell cycle of (5, 8) - (4, 8) - (3, 8) - (3, 9) - (3, 10) - (4, 10) - (4, 9) - (5, 9) - (5, 8).
  Note that the return value must not contain any extra characters. This includes extra spaces in "movements" and extra leading zeros in "R" and "C".