P1686 Challenge

There is not much fun on Peach Blossom Island, so Huang Rong often sneaks into the jianghu to play with Hong Qigong and others. Thus, Huang Yaoshi often comes up with games to play with his daughter, in order to keep Huang Rong by his side — the jianghu is dangerous! This time, Huang Yaoshi devised a simulation game as follows: He divides the entire Peach Blossom Island into a coordinate grid. Before the game starts, Huang Rong stands at a point on the plane, and her boudoir is at another point on the grid. At any time, she can take one step from her current point to one of the four neighboring points: up, down, left, or right. Huang Yaoshi continuously calls out one of four words: “East (E)”, “South (S)”, “West (W)”, “North (N)”, and Huang Rong imagines herself moving from one point to another according to these directions until she reaches her boudoir.  For example, suppose Huang Rong starts at point $\rm A$, and her home is at point $\rm B$. If Huang Yaoshi says the sequence $\verb!NNNENNWWWSSW!$, then she will follow the path shown. Then Huang Yaoshi asks Huang Rong: Did you take any detours in the middle? In other words, is there any shortcut? For example, in the figure there are multiple shortcuts: from $\rm C$ you can go $\verb!NN!$ to reach $\rm E$, or go $\verb!WW!$ directly to $\rm D$. Note: A shortcut must be a straight line. Huang Yaoshi heard that you are a programming expert and would like you to write a program to help him measure the difficulty of this game, so he can improve the rules before letting Huang Rong take on the challenge. Your task is: find one shortest shortcut.

The first line is an integer $n$ ($3 \le n \le 2.5\times 10^5$) representing the length of the string spoken by Huang Yaoshi. The second line is a string consisting of $\verb!N!, \verb!E!, \verb!S!, \verb!W!$, all uppercase letters with no spaces. We label the starting point of the game as $0$, and Huang Rong’s boudoir (the ending point) as $n$. Each intermediate landing point is labeled with a natural number in order.

Output a single line consisting of $3$ numbers and $1$ character, separated by a single space. - The 1st number is the length of the shortest shortcut. - The 2nd number is the starting point of the shortest shortcut. - The 3rd number is the ending point of the shortest shortcut. - The last character is the direction of the shortest shortcut (also one of $\verb!N!, \verb!E!, \verb!S!, \verb!W!$). If there are multiple shortest shortcuts, output the one with the smallest starting point label. If there is still a tie, output the one with the largest ending point label. The testdata guarantees that there exists a shortest shortcut satisfying the conditions.

Translated by ChatGPT 5