From 1be0e964ef4e9cca0a49affbf99a05e2966c4254 Mon Sep 17 00:00:00 2001 From: Raphael McSinyx Date: Sat, 19 Aug 2017 16:18:30 +0700 Subject: Add others/other/nuoc.py --- others/other/nuoc.py | 27 +++++++++++++++++++++++++++ 1 file changed, 27 insertions(+) create mode 100755 others/other/nuoc.py (limited to 'others/other/nuoc.py') diff --git a/others/other/nuoc.py b/others/other/nuoc.py new file mode 100755 index 0000000..9fcff54 --- /dev/null +++ b/others/other/nuoc.py @@ -0,0 +1,27 @@ +#!/usr/bin/env python3 +from heapq import heapify, heappop, heappush + + +with open('NUOC.INP') as f: + m, n = map(int, f.readline().split()) + height = [[int(i) for i in line.split()] for line in f] + +queue = ([(h, 0, i) for i, h in enumerate(height[0])] + + [(h, m - 1, i) for i, h in enumerate(height[-1])] + + [(height[i][0], i, 0) for i in range(m)] + + [(height[i][-1], i, n - 1) for i in range(m)]) +heapify(queue) +visited = ([[True] * n] + + [[True] + [False] * (n - 2) + [True] for _ in range(m - 2)] + + [[True] * n]) +result = 0 + +while queue: + h, i, j = heappop(queue) + for x, y in (i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1): + if 0 <= x < m and 0 <= y < n and not visited[x][y]: + result += max(0, h - height[x][y]) + heappush(queue, (max(height[x][y], h), x, y)) + visited[x][y] = True + +with open('NUOC.OUT', 'w') as f: print(result, file=f) -- cgit 1.4.1