## DMPG '16 S6 - Black and White II

View as PDF

Points: 15 (partial)
Time limit: 1.0s
Memory limit: 64M

Author:
Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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

The board consists of 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 impassible block.

A game board.

Every second, the board moves every block up unit, and wraps them around to . That is, a tile located at at will be at when , and when .

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

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

The goal of the player is to have their block reach .

Hover for a simulation 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 and . The next lines will each contain characters, with . representing a blank space and # representing a block at .

#### Output Specification

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

#### Sample Input 1

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

#### Sample Output 1

1

#### Explanation

Ruby may place a block at to block all of Yang's possible routes.

#### Sample Input 2

5 1
.....

#### Sample Output 2

1

#### Explanation

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

A block must be placed at to prevent Yang from ever being able to finish.

• commented on Sept. 5, 2017, 9:39 p.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

• commented on Sept. 4, 2017, 4: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!

• commented on Sept. 4, 2017, 6: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.

• commented on Sept. 4, 2017, 7: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)?

• commented on Sept. 4, 2017, 8:20 p.m.

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

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

• commented on Sept. 4, 2017, 8:48 p.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!

• commented on Sept. 4, 2017, 9:10 p.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.

• commented on Sept. 4, 2017, 10:12 p.m.

But then that would contradict sample 4.

• commented on Sept. 4, 2017, 10:33 p.m.

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

• commented on Sept. 4, 2017, 11:11 p.m.

I believe that there is still a path if is blocked.

14#.8
#.5..
2#.6#
#.###
3##7.
• commented on Sept. 5, 2017, 12:15 a.m.

(3, 4) would be:

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

Indices start from 0.

• commented on Sept. 5, 2017, 12:57 a.m.

Oops, my bad. Can confirm, one block at makes the game unwinnable.

• commented on Sept. 5, 2017, 9:14 p.m.
• commented on Dec. 2, 2016, 11:02 a.m. edited

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

Is this excluding the red block?

EDIT: Seems so.

• commented on May 18, 2016, 4:09 p.m.

Sample 1 explanation is still wrong

• commented on May 18, 2016, 10:00 p.m.

Sorry for the inconvenience.

• commented on May 18, 2016, 1:53 p.m.

Samples are incorrect