from collections import namedtuple
from queue import PriorityQueue
NORTH, SOUTH, WEST, EAST = (0, -1), (0, 1), (-1, 0), (1, 0)
Cell = namedtuple('Cell', 'level x y')
def max_water_heldover_minheap(heights, display=None):
"""from http://w...content-available-to-author-only...u.com/p/540ee7ec725b"""
q = PriorityQueue()
nrows = len(heights)
ncolumns = len(heights[0])
seen = [[False] * ncolumns for _ in range(nrows)]
# enqueue cells on the perimeter of the island
for y in range(nrows):
seen[y][0] = True
q.put(Cell(heights[y][0], 0, y)) # WEST side
seen[y][ncolumns - 1] = True
q.put(Cell(heights[y][ncolumns - 1], ncolumns - 1, y)) # EAST
for x in range(ncolumns):
seen[0][x] = True
q.put(Cell(heights[0][x], x, 0)) # NORTH side
seen[nrows - 1][x] = True
q.put(Cell(heights[nrows - 1][x], x, nrows - 1)) # SOUTH
# visit all cells once starting with cells with a minimum water level
total = 0
while not q.empty():
cell = q.get()
for dx, dy in [NORTH, SOUTH, WEST, EAST]:
x = cell.x + dx
y = cell.y + dy
if 0 <= y < nrows and 0 <= x < ncolumns and not seen[y][x]:
seen[y][x] = True
q.put(Cell(max(cell.level, heights[y][x]), x, y))
total += max(0, cell.level - heights[y][x])
return total
if __name__ == "__main__":
import sys
heights = [[int(n) for n in line.split()]
for line in sys.stdin if line.strip()]
print(max_water_heldover_minheap(heights))
ZnJvbSBjb2xsZWN0aW9ucyBpbXBvcnQgbmFtZWR0dXBsZQpmcm9tIHF1ZXVlIGltcG9ydCBQcmlvcml0eVF1ZXVlCgpOT1JUSCwgU09VVEgsIFdFU1QsIEVBU1QgPSAoMCwgLTEpLCAoMCwgMSksICgtMSwgMCksICgxLCAwKQoKQ2VsbCA9IG5hbWVkdHVwbGUoJ0NlbGwnLCAnbGV2ZWwgeCB5JykKCmRlZiBtYXhfd2F0ZXJfaGVsZG92ZXJfbWluaGVhcChoZWlnaHRzLCBkaXNwbGF5PU5vbmUpOgogICAgIiIiZnJvbSBodHRwOi8vdy4uLmNvbnRlbnQtYXZhaWxhYmxlLXRvLWF1dGhvci1vbmx5Li4udS5jb20vcC81NDBlZTdlYzcyNWIiIiIKICAgIHEgPSBQcmlvcml0eVF1ZXVlKCkKICAgIG5yb3dzID0gbGVuKGhlaWdodHMpCiAgICBuY29sdW1ucyA9IGxlbihoZWlnaHRzWzBdKQogICAgc2VlbiA9IFtbRmFsc2VdICogbmNvbHVtbnMgZm9yIF8gaW4gcmFuZ2UobnJvd3MpXQoKICAgICMgZW5xdWV1ZSBjZWxscyBvbiB0aGUgcGVyaW1ldGVyIG9mIHRoZSBpc2xhbmQKICAgIGZvciB5IGluIHJhbmdlKG5yb3dzKToKICAgICAgICBzZWVuW3ldWzBdID0gVHJ1ZQogICAgICAgIHEucHV0KENlbGwoaGVpZ2h0c1t5XVswXSwgMCwgeSkpICAjIFdFU1Qgc2lkZQogICAgICAgIHNlZW5beV1bbmNvbHVtbnMgLSAxXSA9IFRydWUKICAgICAgICBxLnB1dChDZWxsKGhlaWdodHNbeV1bbmNvbHVtbnMgLSAxXSwgbmNvbHVtbnMgLSAxLCB5KSkgICMgRUFTVAoKICAgIGZvciB4IGluIHJhbmdlKG5jb2x1bW5zKToKICAgICAgICBzZWVuWzBdW3hdID0gVHJ1ZQogICAgICAgIHEucHV0KENlbGwoaGVpZ2h0c1swXVt4XSwgeCwgMCkpICAjIE5PUlRIIHNpZGUKICAgICAgICBzZWVuW25yb3dzIC0gMV1beF0gPSBUcnVlCiAgICAgICAgcS5wdXQoQ2VsbChoZWlnaHRzW25yb3dzIC0gMV1beF0sIHgsIG5yb3dzIC0gMSkpICAjIFNPVVRICgogICAgIyB2aXNpdCBhbGwgY2VsbHMgb25jZSBzdGFydGluZyB3aXRoIGNlbGxzIHdpdGggYSBtaW5pbXVtIHdhdGVyIGxldmVsCiAgICB0b3RhbCA9IDAKICAgIHdoaWxlIG5vdCBxLmVtcHR5KCk6CiAgICAgICAgY2VsbCA9IHEuZ2V0KCkKICAgICAgICBmb3IgZHgsIGR5IGluIFtOT1JUSCwgU09VVEgsIFdFU1QsIEVBU1RdOgogICAgICAgICAgICB4ID0gY2VsbC54ICsgZHgKICAgICAgICAgICAgeSA9IGNlbGwueSArIGR5CiAgICAgICAgICAgIGlmIDAgPD0geSA8IG5yb3dzIGFuZCAwIDw9IHggPCBuY29sdW1ucyBhbmQgbm90IHNlZW5beV1beF06CiAgICAgICAgICAgICAgICBzZWVuW3ldW3hdID0gVHJ1ZQogICAgICAgICAgICAgICAgcS5wdXQoQ2VsbChtYXgoY2VsbC5sZXZlbCwgaGVpZ2h0c1t5XVt4XSksIHgsIHkpKQogICAgICAgICAgICAgICAgdG90YWwgKz0gbWF4KDAsIGNlbGwubGV2ZWwgLSBoZWlnaHRzW3ldW3hdKQoKICAgIHJldHVybiB0b3RhbAoKaWYgX19uYW1lX18gPT0gIl9fbWFpbl9fIjoKICAgIGltcG9ydCBzeXMKICAgIGhlaWdodHMgPSBbW2ludChuKSBmb3IgbiBpbiBsaW5lLnNwbGl0KCldCiAgICAgICAgICAgICAgIGZvciBsaW5lIGluIHN5cy5zdGRpbiBpZiBsaW5lLnN0cmlwKCldCiAgICBwcmludChtYXhfd2F0ZXJfaGVsZG92ZXJfbWluaGVhcChoZWlnaHRzKSkK