RookGraph
SRM 657 · 2015-03-26 · by rng_58
SRM 657 · 2015-03-26 · by rng_58 · Dynamic Programming
Problem Statement
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 aString[] 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 theint N and the String[] graph.
Return the number of ways to place the rooks, modulo 1,000,000,007.
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
You are given the
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
0)
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.
1)
8
{"111",
"110",
"101"}
Returns: 6272
2)
2
{"11111",
"11111",
"11111",
"11111",
"11111"}
Returns: 0
The board is too small for 5 rooks.
3)
10
{"1010000100",
"0100101000",
"1011010100",
"0011010000",
"0100100000",
"0011010010",
"0100001001",
"1010000110",
"0000010110",
"0000001001"}
Returns: 289151874
4)
50
{"10111110000",
"01011010000",
"10100010011",
"11010110001",
"11001100101",
"10011100110",
"11110011111",
"00000011100",
"00001111100",
"00100110010",
"00111010001"}
Returns: 0
Submissions are judged against all 137 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class RookGraph with a public method int countPlacements(int N, vector<string> graph) · 137 test cases · 2 s / 256 MB per case