The Rocky Horror Picture Show P16636


pdf   zip

If you’re staying at Dr. Frank N. Furter’s place, you’d better watch your step! The moment the music kicks in, just look at the squares on the floor, join the other guests, follow the dance moves, and…let’s do the Time Warp again!

But hey, there are so many ways you can literally get warped and be sent back to Transsexual Transylvania:

  • If you hit any of the room walls (then you get warped!).
  • If you bump into another guest mid-air as you try to swap your positions (then you both get warped before you can land on your target square!).
  • If you land your step in the same square as other guests (then you all get warped!)

Given how all guests are at the start of the dance, can you tell how many of you would remain on the dance floor if the music went on forever?


Input begins with the number of cases n ≥ 0. For every case, we have the dimensions W and H of the room, followed by the number of people P, followed by P triplets xi, yi, bi with the position of the dancer and the direction he or she is facing. Follow the number of steps S in the dance, followed by S characters si ∈ {‵F′, ‵R′, ‵B′, ‵L′} denoting a step forward, right, backward, or left, respectively.

Assume that W and H are between 1 and 106, 1 ≤ P ≤ 104, 1 ≤ xiW, 1 ≤ yiH, bi ∈ {‵N′, ‵E′, ‵S′, ‵W′}, 1 ≤ S ≤ 104, and that no two dancers will start at the same position.


For each case, print the number of people that will be dancing indefinitely without ever being warped.

Public test cases
  • Input

    6 5
    3  2 2 E  2 4 N  5 3 W
    4  R F L B
    6 5
    3  2 3 E  2 4 N  4 3 W
    4  R F L B


  • Information
    Edgar Gonzàlez
    Official solutions
    User solutions