2015 Canadian Computing Olympiad
Day 2, Problem 1 - Cars on Ice
Guarding a bank during Christmas night can get very boring. That's why Barry decided to go skating around the parking lot for a bit. However the parking lot isn't empty as the other security guards have their cars parked there. So Barry decides to push their cars out of the parking lot. He notices that their cars are parked facing either North, South, East or West. Since the parking lot is frozen, pushing a car will make it slide until it has left the parking lot or hit another car. Cars can only be pushed in the direction which they are facing. Not wanting to crash the cars, Barry enlists your help to find out what order he has to push the cars so as to clear the parking lot.
Input Format
The first line contains two integers, N and M (1 ≤ N, M ≤ 2000), representing the number of rows and columns of the parking lot. The next N lines each contain M characters representing the parking lot itself, where '.' represents an empty spot, while 'N', 'S', 'E', and 'W' each represent a car (facing North, South, East or West, respectively).
For at least 70% of the marks for this problem, N ≤ 100 and M ≤ 100.
Output Format
Output the order in which the cars have to be pushed so as to clear the parking lot without crashes. Output each car in the form (r, c), where r and c are the car's coordinates on the parking lot (where (0, 0) is the top leftmost spot and (N − 1, M − 1) is the bottom rightmost spot).
You can assume there will always be at least one valid solution.
If there are multiple possible solutions, output any valid solution.
Sample Input 1
5 5 ..... .E.S. ..... ..... .N.E.
Sample Output 1
(4,3) (1,3) (1,1) (4,1)
Explanation for Sample 1
The only car that isn't initially blocked by another car is the one at (4,3). After that's pushed out to the right side of the parking lot, then the car above it (at (1, 3)) can be pushed, and then the one at (1, 1), and finally the car at (4, 1), clearing the parking lot.
Sample Input 2
4 3 ... .N. .S. ...
Sample Output 2
(1,1) (2,1)
Explanation for Sample 2
Either car could be pushed first to clear the parking lot, so this output is acceptable (as would the output with the lines outputted in reverse order).
All Submissions
Best Solutions
Point Value: 15 (partial)
Time Limit: 3.00s
Memory Limit: 256M
Added: Jun 05, 2015
Author: David Pritchard
Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3
Comments (Search)