LCC/Moose '19 Contest 1 S3 - Chomp

View as PDF

Submit solution


Points: 12 (partial)
Time limit: 3.0s
Memory limit: 256M

Author:
Problem types

Alice and Bob recently bought a few chocolate bars that they want to share and they decided to make a game out of eating them. Starting with Alice, they take turns picking a square of the bar, breaking off all of the squares above and/or to the right of that square, and eating the broken off pieces. The person who eats the last square loses. Here are two examples of valid moves (selected square marked with X):

###     #..   ...     ...
#X# --> #.. , ##. --> #..
###     ###   #X#     #..

Alice and Bob have already eaten parts of the chocolate bars. They would like to know who would win for each chocolate bar if they both play optimally.

Input Specification

The first line of input contains an integer T (1 \le T \le 10), the number of chocolate bars they have. T descriptions of chocolate bars follow: each description begins with two integers R, C (1 \le R, C\le 6), the number of rows and columns in the chocolate bar. The next R lines each contain C characters containing # if that square is still present, or . if it is already eaten. It is guaranteed that there is at least one present square and that for every present square, every square below and/or to the left of it will also be present.

For 40 of 100 points, R*C \le 10.

Output Specification

For each chocolate bar, output Alice if Alice would win; or Bob otherwise.

Sample Input 1

3
2 2
##
##
2 2
#.
##
2 4
##..
####

Sample Output 1

Alice
Bob
Alice

Explanation of Sample Input

In the second case, Alice can either break off the top left square, bottom right, or bottom left squares. The bottom left would cause her to lose instantly. Picking top-left/bottom-right would cause Bob to pick the other, leaving only the bottom left square, so she'd be forced to finish the bar.

In the first case, Alice can break at the top-right square, leaving Bob in the second case, which we saw is losing above.


Comments

There are no comments at the moment.