P5474 [CCO 2015] Cars on Ice

**This problem is translated from [CCO 2015](https://cemc.math.uwaterloo.ca/contests/computing/2015/index.html) Day2 T1 "[Cars on Ice](https://cemc.math.uwaterloo.ca/contests/computing/2015/stage%202/day2.pdf)".** Guarding a bank on Christmas Eve is very boring. That is why Barry wants to go skating near the parking lot. However, because other guards parked their cars there, the parking lot is not empty. So Barry decides to push their cars out of the parking lot. He notices that the parked cars are facing one of the four directions: north, south, east, or west. Since the parking lot is icy, pushing a car will make it slide until it leaves the parking lot or crashes into another car. Each car can only be pushed in the direction it is facing. To avoid crashes, Barry asks you for help: compute an order to push the cars out of the parking lot so that he can clear the entire lot.

The first line contains two integers $N, M$, representing the number of rows and columns of the parking lot. The next $N$ lines each contain $M$ characters describing the parking lot. `.` means an empty space, and `N`, `E`, `W`, `S` indicate a car, meaning the car is facing north, east, west, and south, respectively.

Output an order to push the cars out without any crashes. Output each car in the format $(r,c)$, where $(r,c)$ is the car’s coordinate in the parking lot. $(0,0)$ is the top-left corner and $(N-1,M-1)$ is the bottom-right corner. It is guaranteed that there is at least one valid solution. If there are multiple solutions, output any one.

#### Sample Explanation 1 The only car that is not blocked by any other car at the start is the car at $(4,3)$. After this car is pushed out through the right side of the parking lot, the car above it (the car at $(1,3)$) can be pushed out, then the car at $(1,1)$, and finally the car at $(4,1)$. The parking lot is then cleared. #### Sample Explanation 2 Either car can be the first car pushed out of the parking lot, so Sample Output 2 is correct. The output in the reverse order is also correct. #### Constraints For $70\%$ of the testdata, $1 \le N, M \le 100$. For $100\%$ of the testdata, $1 \le N, M \le 2000$. Translated by ChatGPT 5