#636 · Grids and matrices · Advanced · Fast enough · 145 XP · about 30 min
An orchard is planted on a grid. grid is a list of rows, and grid[r][c] is 1 if a tree grows at row r, column c, and 0 if the spot is empty. A buyer wants to know how many trees are in each of many rectangular plots. A plot is a tuple (top, left, bottom, right): it covers rows top to bottom and columns left to right, edges included.
Write trees_in_plots(grid, plots) that returns a list with the number of trees in each plot, in order.
grid = [ [1, 0, 1], [0, 1, 1], [1, 1, 0], ] trees_in_plots(grid, [(0, 0, 2, 2), (1, 1, 2, 2), (0, 2, 0, 2)]) # returns [6, 3, 1]
The first plot is the whole orchard, the second is the two by two square at the bottom right, and the third is the single spot at row 0, column 2.
0 <= len(plots) <= 100,0000 <= top <= bottom < rows and 0 <= left <= right < columnsEach test must finish within 10 seconds, and the hidden tests ask about 100,000 plots of an 800 by 800 orchard.
First solves only, ranked by stars and then time.