CCO '15 P4 - Cars on Ice

View as PDF
Submit solution
Points: 15 (partial)
Time limit: 7.0s
Memory limit: 512M
Problem type
Canadian Computing Olympiad: 2015 Day 2, Problem 1

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 Specification

The first line contains two integers N and M (1 \le N,M \le 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 \le 100 and M \le 100.

Output Specification

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.

Output for Sample Input 1

(4,3)
(1,3)
(1,1)
(4,1)

Explanation for Output for Sample Input 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.
...

Output for Sample Input 2

(1,1)
(2,1)

Explanation for Output for Sample Input 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).

Comments


  • 1
    Darcy_Liu  commented on Jan. 20, 2020, 5:54 p.m. ← edit 3

    Passed TC 10 with iteration, not with recursion


  • -7
    p1geon  commented on Feb. 12, 2019, 2:13 p.m.

    This comment is hidden due to too much negative feedback. Click here to view it.


    • 5
      Zeyu  commented on Feb. 12, 2019, 6:32 p.m. ← edited

      Yes it is possible! In pypy2 the worst test took ~3 seconds.


  • -1
    anasschoukri2  commented on Jan. 28, 2018, 2:03 p.m.

    I can't understand,I submit the same code, once 60/100 , other with 50/100


  • -2
    anasschoukri2  commented on Jan. 28, 2018, 10:34 a.m.

    what if the car is already in the place we want to put it in


    • 4
      injust  commented on Jan. 28, 2018, 11:03 a.m.

      That can't be the case, you're trying to clear the board of cars.


  • 3
    Cueball1234  commented on Jan. 26, 2018, 10:18 p.m. ← edit 8

    Strange WA and TLE

    I submitted my solution and got 90/100 (Case #10 TLE). I submitted again (exact same code) and got 60/100 (Case #7-9 WA, #10 TLE).

    Moreover, my solution runs at O(MN), which should theoretically be fast enough. Is it because the compiler today is slow? Could someone please take a look at my solution? Thank you!

    (And it says that for case #10 I used around 400 MB, but I have no idea how)


    • 3
      max  commented on Jan. 27, 2018, 3:26 a.m. ← edit 2

      Yeah, I just submitted a code which has complexity O(mn) and recieved a TLE for case 10 as well.

      Edit: Just submitted my code a couple more times and my program's runtimes have been all over the place.


  • 1
    anishmahto  commented on June 27, 2016, 5:09 p.m.

    Well, this is new... What does the following error mean?

    Test case #7: MLE (tgkill syscall disallowed) [2.945s, 572.64 MB] (0/10) Test case #8: MLE (tgkill syscall disallowed) [3.453s, 572.61 MB] (0/10) Test case #9: MLE (tgkill syscall disallowed) [2.612s, 529.22 MB] (0/10) Test case #10: MLE (tgkill syscall disallowed) [2.470s, 569.34 MB] (0/10)

    The other test cases got an AC.

    Gotta love it when your code breaks more things than it solves :D


    • 2
      Xyene  commented on June 27, 2016, 7:09 p.m. ← edit 2

      The error appears to have appeared after I updated runtimes yesterday. See here for more details on it. For now, treat all tgkill errors as MLEs.

      Update: the error has been worked around; now you'll either see MLE or RTE (Segmentation fault) depending on your scenario.


    • 2
      Bami  commented on June 27, 2016, 6:50 p.m.

      It's a Memory Limit Error. You went over the allowed 512M


      • 3
        anishmahto  commented on June 27, 2016, 9:21 p.m.

        Thanks guys, that makes sense.


  • 8
    bruce  commented on June 21, 2016, 8:32 p.m.

    It seems that the special judge is fixed. Thanks, DMOJ admins!