Square Game

Submit solution

Points: 1
Time limit: 5.0s
Memory limit: 512M

Problem type

Connie and Max are both quite bored after a day of boorish behavior and have decided to play a board game. The game is played on a checkerboard with \(R\) rows and \(C\) columns. The game is played by placing squares (these could be \(1\times1\), or \(2\times2\), and so on) of any size on the board. At the beginning of the game, certain grid locations are marked as out-of-bounds and cannot have any square placed over them. The players take turns placing squares. Squares must be placed in a way to lines up with the checkerboard grid. A player's square must fit properly onto the game grid, and cannot overlap, or be placed on top of, an existing square placed in a previous turn. The winner is the player who places the last square. If all the cells in the grid are out-of-bounds, then the game ends immediately after beginning, and a coin flip determines the winner. Note that when the last square is placed, the game board will be completely covered by squares, with the exception of the out-of-bounds cells. Connie and Max would like to know how many unique configurations there are of their game board after any game has finished. Your job is to write a program to compute the number of these configurations modulo \(10^9+7\).

Consider a \(3\times 3\) game board in which the bottom right cell is out-of-bounds. There are four game ending configurations. We could have \(1\times 1\) squares on every cell, a \(2\times 2\) square in the top right, top left, or bottom left. Thus, four configurations. Now, consider the case where the bottom right cell is not out-of-bounds. There are six configurations. There are the four already mentioned for the previous example, and one could place a \(2\times 2\) square on the bottom right corner, or cover the entire board with one \(3\times 3\) square.

Input Specification

The first line of input contains two integers separated by a space, \(R\) (\(1\leq R\leq 14\)) and \(C\) (\(1\leq C\leq 14\)). Following this are \(R\) lines, each with \(C\) space separated integers whose value is either \(0\) or \(1\). If the \(c\)th integer on line \(r\) is \(1\), then the checkerboard grid location \(r,c\) is valid, and if it is \(0\), then the location is out-of-bounds.

Output Specification

Output a single integer: the number of game ending configurations modulo \(10^9+7\).

Sample Input 1

3 3
1 1 1
1 1 1
1 1 0

Sample Output 1


Sample Input 2

3 3
1 1 1
1 1 1
1 1 1

Sample Output 2



There are no comments at the moment.