DMPG '16 S6 - Black and White II - DMOJ: Modern Online Judge

DMPG '16 S6 - Black and White II

View as PDF

Submit solution

All submissions

Best submissions

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$ $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$ $1$ unit, and wraps them around to $N-1$ $N - 1$ . That is, a tile located at $(0, 1)$ $(0, 1)$ at $t = 0$ $t = 0$ will be at $(0, 0)$ $(0, 0)$ when $t = 1$ $t = 1$ , and $(0, N-1)$ $(0, N - 1)$ when $t = 2$ $t = 2$ .

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

Every second, the player may move their red piece by at most $1$ $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$ $t$ so long as their current position is not covered by a wall at $t+1$ $t + 1$ .

The goal of the player is to have their block reach $x = M-1$ $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$ $M$ and $N$ $N$ $(1 \le M, N \le 100)$ $(1 \leq M, N \leq 100)$ . The next $N$ $N$ lines will each contain $M$ $M$ characters, with . representing a blank space and # representing a block at $t=0$ $t = 0$ .

Output Specification

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

Sample Input 1

Copy

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

Sample Output 1

Copy

Explanation for Sample Output 1

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

Sample Input 2

Copy

5 1
.....

Sample Output 2

Copy

Explanation for Sample Output 2

Placing any block will make the game unwinnable.

Sample Input 3

Copy

3 3
.#.
.##
..#

Sample Output 3

Copy

Sample Input 4

Copy

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

Sample Output 4

Copy

Explanation for Sample Output 4

A block must be placed at $(1, 0)$ $(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:

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)?

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$ $t = 0$ , the adjacent cell must be empty at $t=0$ $t = 0$ , not after the rotation at $t=1$ $t = 1$ .

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

0
Cueball1234 commented on Sept. 5, 2017, 12:48 a.m. ← edited →
So just confirming, the following case is allowed:

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

But this case is not:

Copy
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)$ $(3, 4)$ is blocked.

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

1
wleung_bvg commented on Sept. 5, 2017, 4:15 a.m.
(3, 4) would be:

Copy
5 5 ..#.. #.... .#..# #..## .###.

Indices start from 0.

2

injust commented on Sept. 5, 2017, 4:57 a.m.

Oops, my bad. Can confirm, one block at $(3,4)$ $(3, 4)$ makes the game unwinnable.

-3

Xue_Alex commented on Sept. 6, 2017, 1:14 a.m.

https://dmoj.ca/problem/helloworld#comment-5742

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.