RookGraph | Topcoder Archive

Problem Statement

Cat Snuke has an N times N chessboard. He is going to place K rooks numbered 0 through K-1 onto the chessboard. (Note that the rooks are distinguishable.)

Obviously, he cannot put two rooks onto the same square of the chessboard. There are some additional restrictions he also has to obey. You are given these in a String[] graph with K elements, each containing K characters. For each i and j, graph[i][j] is either '1' or '0'. If graph[i][j] is '1', rooks i and j must be in the same row or column. If graph[i][j] is '0', rooks i and j must be neither in the same row, nor in the same column.

You are given the int N and the String[] graph. Return the number of ways to place the rooks, modulo 1,000,000,007.

Definition

Class:: RookGraph
Method:: countPlacements
Parameters:: int, String[]
Returns:: int
Method signature:: int countPlacements(int N, String[] graph)
(be sure your method is public)

Constraints

N will be between 1 and 50, inclusive.
graph will contain between 1 and 50 elements, inclusive.
Each element of graph will contain exactly K characters, where K is the number of elements of graph.
Each character in graph will be either '0' or '1'.
For each i, the i-th character of the i-th element of graph will be '1'.
For each i and j, the j-th character of the i-th element of graph and the i-th character of the j-th element of graph will be the same.

Examples

```
8
```
```
{"11",
 "11"}
```
```
Returns: 896
```
There are 64 ways to put rook 0, and for each possible position of rook 0 there are 14 ways to put rook 1. Thus, the answer is 64 * 14 = 896.
```
8
```
```
{"111",
 "110",
 "101"}
```
```
Returns: 6272
```

{"11111",
 "11111",
 "11111",
 "11111",
 "11111"}

Returns: 0

The board is too small for 5 rooks.

{"1010000100",
 "0100101000",
 "1011010100",
 "0011010000",
 "0100100000",
 "0011010010",
 "0100001001",
 "1010000110",
 "0000010110",
 "0000001001"}

Returns: 289151874

{"10111110000",
 "01011010000",
 "10100010011",
 "11010110001",
 "11001100101",
 "10011100110",
 "11110011111",
 "00000011100",
 "00001111100",
 "00100110010",
 "00111010001"}

Returns: 0

{"10000000000000000000000000000000000000000000000000",
 "01000000000000000000000000000000000010000000010000",
 "00100000000010000000000100001100000000010010000000",
 "00010000000010000000001000000000000000000000000000",
 "00001000000000000000000000000000000000100000000000",
 "00000100101000000010000000000000000000100100000001",
 "00000010000000000100000001000000000000000000000001",
 "00000001000000001000000000000000000000000000000100",
 "00000100101000000000000000000000000000000000000001",
 "00000000010000000000000010000010000000000000100000",
 "00000100101000000000000000000010000000000000000001",
 "00000000000100000010000100001000000001001000100000",
 "00110000000010000000001000001000000000000010000000",
 "00000000000001000000000000000000000000000000000000",
 "00000000000000100000000000000000001010000000000010",
 "00000000000000010000000000100000000000000000000000",
 "00000001000000001000000000000000000000010000000000",
 "00000010000000000100000001000000010000000000000000",
 "00000100000100000010000000001000000001101100000000",
 "00000000000000000001000000000001000000000000001100",
 "00000000000000000000110000000000100000000000000010",
 "00000000000000000000110010000000100000000010000000",
 "00010000000010000000001000000001000000000001000000",
 "00100000000100000000000100000100000000010000100000",
 "00000000010000000000010011000000000000000010000000",
 "00000010000000000100000011000000000000000000000000",
 "00000000000000010000000000100000001000001000000000",
 "00000000000000000000000000010000010100000000000000",
 "00100000000110000010000000001000000001001010000000",
 "00100000000000000000000100000100000000010000000000",
 "00000000011000000000000000000010000000000000100000",
 "00000000000000000001001000000001000000000001001100",
 "00000000000000000000110000000000100100000000000000",
 "00000000000000000100000000010000010000000000000000",
 "00000000000000100000000000100000001000001000000000",
 "00000000000000000000000000010000100100000000000000",
 "01000000000000100000000000000000000010000000010010",
 "00000000000100000010000000001000000001001000000000",
 "00001100000000000010000000000000000000100100000000",
 "00100000000000001000000100000100000000010000000000",
 "00000000000100000010000000101000001001001000000000",
 "00000100000000000010000000000000000000100100000000",
 "00100000000010000000010010001000000000000010000000",
 "00000000000000000000001000000001000000000001000000",
 "00000000010100000000000100000010000000000000100000",
 "01000000000000000000000000000000000010000000010000",
 "00000000000000000001000000000001000000000000001100",
 "00000001000000000001000000000001000000000000001100",
 "00000000000000100000100000000000000010000000000010",
 "00000110101000000000000000000000000000000000000001"}

Returns: 0

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.