DMPG '16 S6 - Black and White II

View as PDF
Submit solution
Points: 15 (partial)
Time limit: 1.0s
Memory limit: 64M
Author:
Xyene
Problem types

Ruby and her sister Yang are playing with a mechanized board game.

The board consists of M \times N square cells of unit dimensions on a plane, with the origin defined as the topmost left tile. Some of these cells are originally colored black, signifying an impassable block.


A game board.

Every second, the board moves every block up 1 unit, and wraps them around to N-1. That is, a tile located at (0, 1) at t = 0 will be at (0, 0) when t = 1, and (0, N-1) when t = 2.

A player may start the game by placing a red piece on any clear tile where x = 0. A player may move their piece to a tile X at time t if and only if X is clear (i.e., does not contain a wall) at t. Likewise, the starting position must be clear at t = 0.

Every second, the player may move their red piece by at most 1 unit every second in cardinal directions, with the player's piece wrapping around the board like wall blocks do. A player may keep their piece stationary at time t so long as their current position is not covered by a wall at t+1.

The goal of the player is to have their block reach x = M-1.

Hover for a simulation of a game.
Please visit https://www.dmoj.ca/problem/dmpg16s6 for an animation of a game.

Ruby is playing Yang. Since they recently argued over something petty, Ruby wants to get back at Yang by making the game impossible for Yang to finish. To this end, she will be placing — while Yang is not looking — a number of new wall blocks to cut off Yang's movement. How many blocks does she need, if she wants to use as few as possible to make the game unwinnable?

Input Specification

The first line of input will contain two space-separated integers M and N (1 \le M, N \le 100). The next N lines will each contain M characters, with . representing a blank space and # representing a block at t=0.

Output Specification

A single integer; the number of blocks Ruby needs to place.

Sample Input 1

5 2
..#..
.....

Sample Output 1

1

Explanation for Sample Output 1

Ruby may place a block at (2, 1) to block all of Yang's possible routes.

Sample Input 2

5 1
.....

Sample Output 2

1

Explanation for Sample Output 2

Placing any block will make the game unwinnable.

Sample Input 3

3 3
.#.
.##
..#

Sample Output 3

1

Sample Input 4

5 5
..#..
#....
.#..#
#..##
.##..

Sample Output 4

1

Explanation for Sample Output 4

A block must be placed at (1, 0) to prevent Yang from ever being able to finish.

Comments


  • 0
    Cueball1234  commented on Sept. 6, 2017, 1:39 a.m. ← edit 3

    Sorry, just some more confirmations:

    1. Is the piece allowed to go off the bottom and enter from the top (clarifying since technically a block does not do that move, rather off the top and enter from the bottom)?

    2. Is this allowed:

      Time t

      R

      #

      Time t+1

      #

      R

    Can it go through the block?

    Edit: Answers to both questions are yes


  • 0
    Cueball1234  commented on Sept. 4, 2017, 8:33 p.m.

    Is Sample Input 4 correct?

    Even if you place a block at (1,0), you can start at the topmost leftmost tile and move "Right Right Stay Right Right".

    Am I reading the problem wrong? Thank you!


    • 1
      injust  commented on Sept. 4, 2017, 10:26 p.m.

      If there is a block at (1,0), you cannot start at the top-left tile and move right, because you would then encounter said block.


      • 0
        Cueball1234  commented on Sept. 4, 2017, 11:03 p.m. ← edited

        But don't the blocks move up 1 unit every second so that at t=1, the said block is at (1,N-1) and the player is at (1,0)?


        • 1
          injust  commented on Sept. 5, 2017, 12:20 a.m.

          To move a piece when t=0, the adjacent cell must be empty at t=0, not after the rotation at t=1.

          "A player may move their piece to a tile X at time t if and only if X is clear…at t."


          • 0
            Cueball1234  commented on Sept. 5, 2017, 12:48 a.m. ← edited

            So just confirming, the following case is allowed:

            Time t          Time t+1
R .             .  R#
. #             .  .

            But this case is not:

            Time t          Time t+1
. .             .  #
R #             .  R

            Also, it seems that in the simulation of the game, state t=9 to t=10 matches the latter case.

            Thank you!


            • 1
              injust  commented on Sept. 5, 2017, 1:10 a.m. ← edited

              Scratch what I said earlier. After reviewing the simulation, I have come to the conclusion that I have no idea how any of this works.

              It seems like any move is allowed as long as the destination tile will be clear after the next shift.


              • 0
                Cueball1234  commented on Sept. 5, 2017, 2:12 a.m.

                But then that would contradict sample 4.


                • 1
                  wleung_bvg  commented on Sept. 5, 2017, 2:33 a.m.

                  I believe the correct square to be blocked is (3, 4), but could someone else confirm?


                  • 1
                    injust  commented on Sept. 5, 2017, 3:11 a.m.

                    I believe that there is still a path if (3,4) is blocked.

                    14#.8
#.5..
2#.6#
#.###
3##7.

  • 0
    mmun  commented on Dec. 2, 2016, 4:02 p.m. ← edited

    Every second, the board moves every block up 1 unit...

    Is this excluding the red block?

    EDIT: Seems so.