Rooks on a rampage def safe_squares_rooks(n, rooks): A generalized n-by-n chessboard has been invaded by a parliament of rooks, each rook represented as a two-tuple (row, column) of the row and the column of the square that the rook is in. Since we are again computer programmers instead of chess players and other normal folks, our rows and columns are numbered from 0 to n - 1. A chess rook covers all squares that are in the same row or in the same column. Given the board size n and the list of rooks on that board, count the number of empty squares that are safe, that is, are not covered by any rook. To achieve this in reasonable time and memory, you should count separately how many rows and columns on the board are safe from any rook. Because permuting the rows and columns does not change the answer to this question, you can imagine all these safe rows and columns to have been permuted to form an empty rectangle at the top left corner of the board. The area of that safe rectangle is then obviously the product of its known width and height. n rooks Expected result 10 [] 100 4 [(2, 3), (0, 1)] 4 8 [(1, 1), (3, 5), (7, 0), (7, 6)] 20 2 [(1, 1)] 1 6 [(r, r) for r in range(6)] 0 100 [(r, (r*(r-1))%100) for r in range(0, 100, 2)] 3900 10**6 [(r, r) for r in range(10**6)] 0
Rooks on a rampage
def safe_squares_rooks(n, rooks):A generalized n-by-n chessboard has been invaded by a parliament of rooks, each rook represented as a two-tuple (row, column) of the row and the column of the square that the rook
is in. Since we are again computer programmers instead of chess players and other normal folks, our rows and columns are numbered from 0 to n - 1. A chess rook covers all squares that are in the same row or in the same column. Given the board size n and the list of rooks on that board, count the number of empty squares that are safe, that is, are not covered by any rook.
To achieve this in reasonable time and memory, you should count separately how many rows and columns on the board are safe from any rook. Because permuting the rows and columns does not change the answer to this question, you can imagine all these safe rows and columns to have been permuted to form an empty rectangle at the top left corner of the board. The area of that safe rectangle is then obviously the product of its known width and height.
|
n |
rooks |
Expected result |
|
10 |
[] |
100 |
|
4 |
[(2, 3), (0, 1)]
|
4 |
|
8 |
[(1, 1), (3, 5), (7, 0), (7, 6)]
|
20 |
|
2 |
[(1, 1)] |
1 |
|
6 |
[(r, r) for r in range(6)]
|
0 |
|
100 |
[(r, (r*(r-1))%100) for r in range(0, 100, 2)]
|
3900 |
|
10**6 |
[(r, r) for r in range(10**6)]
|
0 |
Trending now
This is a popular solution!
Step by step
Solved in 3 steps
