Ctrl K

Pyramid Plots in a Field

Hard
A field is given as a matrix field of zeros and ones: 1 is a fertile cell, 0 is a barren one. Everything outside the field counts as barren. A **pyramid** of height h ≥ 2 with its top at (r, c) covers h consecutive rows going down from row r: in row r + d (for d from 0 to h - 1) it covers columns c - d through c + d. So one cell on top, three below it, five below those, and so on. An **upside-down pyramid** is the same shape growing upwards: its tip (r, c) is the bottom cell, and in row r - d it covers columns c - d through c + d. A plot is usable if all of its cells are fertile. Count all usable pyramids and upside-down pyramids together. Plots of different heights sharing a top are counted separately.
Example 1
field=[[0, 1, 0], [1, 1, 1]] → 1

One pyramid: its top is at (0, 1) with the whole of row 1 beneath it. No upside-down one fits, since row 0 has zeros.

Example 2
field=[[1, 1, 1], [1, 1, 1], [1, 1, 1]] → 4

Height-2 pyramids with tops at (0, 1) and (1, 1), and upside-down height-2 ones with tips at (1, 1) and (2, 1). Height 3 does not fit: its widest row would need 5 cells.

Example 3
field=[[1, 1], [1, 1]] → 0

The row below a top must be 3 cells wide, but the field has only 2 columns.

Constraints
  • 1 ≤ number of rows, number of columns ≤ 1000
  • rows × columns ≤ 4 · 10⁵
  • field[i][j] is 0 or 1
Have you seen this problem in a real interview?
Solved by0
Tried by0
Submissions0
Acceptance—
Topics
Similar problemsBiggest Solid Panel Block HardCrossing the Cave HardLongest Uphill Walk HardWeeks of Rest by Flight HardBerry Field Round Trip Hard
loading Python…
Input
field=[[0, 1, 0], [1, 1, 1]]
Expected
1

Run checks the first 3 tests in your browser. Submit checks all 77 tests on the server, hidden ones included.