У меня есть куча шестигранных стержней, склеенных в странную скульптуру. Стержни имеют длину от 1 до 99 сантиметров (см) и площадь поперечного сечения 1 квадратный см. Все стержни приклеены на шестиугольную поверхность как минимум к одному другому стержню. Все стержни выровнены по нижнему краю.

После сильного дождя скульптура полна воды. Сколько воды в нем содержится?

вход

Ваша программа должна прочитать (через стандартный ввод или файл) количество строк, состоящих из пар пробелов и пар цифр, определяющих длину стержней в этом формате:

  aa  bb
cc  dd  ee
  ff  gg

Каждый стержень (как здесь dd) приклеен максимум к 6 окружающим стержням, как показано в примерах. Недостающие стержни являются отверстиями и не собирают воду. Например, вход

  04  04
04  01  03
  04  04

будет представлять следующую скульптуру:

Центральный стержень - высота 1(я не нашел хорошего угла, где этот стержень также виден). Теперь колонна над этим стержнем может вмещать 2 см воды, прежде чем она начнет переливаться через 3стержень справа. Поскольку ни один из других стержней не может удерживать над ними воду, ответ будет 2. Вот два более сложных примера:

Example 2:
55  34  45  66
  33  21  27
23  12  01  77
  36  31  74
answer = 35 (  2 on top of 21 
             +11 on top of 12
             +22 on top of 01, before everything overflows over 23)

Example 3:
        35  36  77  22                      23  32  54  24
      33  07  02  04  21                  54  07  07  07  76
    20  04  07  07  01  20              54  11  81  81  07  76
  20  67  67  22  07  01  78          54  07  81  07  81  09  76
20  67  07  67  22  22  07  44  55  54  07  81  07  07  61  07  20
  67  57  50  50  07  07  14  03  02  15  81  99  91  07  81  04
67  07  50      50  87  39  45  41  34  81  07  07  89  07  81  79
  67  07  50  50  07  07  07  27  07  27  81  07  07  79  81  78
20  67  67  07  07  07  07  99  33  46  02  81  07  07  81  01  20
  33  07  07  01  05  01  92          20  02  81  07  81  15  32
    22  07  20  20  07  20              63  02  80  81  15  32
      45  20  01  20  39                  20  15  07  15  32
        23  20  20  29  43  21  18  41  20  66  66  43  21
      90                  99  47  07  20
    50                      20  02  48
  70                          56  20
                                90

answer = 1432

Выход

Ваша программа должна вывести единственное целое число, дающее объем воды в кубических сантиметрах.

Гол

Ваша оценка - это количество байтов вашего исходного кода. Самые низкие победы.

Стандартные лазейки, как обычно, запрещены.

Эта головоломка была вдохновлена вопросом SPOJ .

Python 2, 222 байта

import sys
y=h=v=0;B={}
for l in sys.stdin:
 z=y;y+=2j
 while l:
    if"0"<l:B[z]=int(l[:2])
    l=l[2:];z+=1
while B:C=B;B={b:B[b]for b in B if(h<B[b])+sum(3>abs(c-b)for c in B)/7};a=C==B;h+=a;v+=a*sum(h>B[b]for b in B)
print v

Считывает ввод через STDIN и записывает результат в STDOUT.

объяснение

Мы начинаем с нуля и постепенно увеличиваем уровень воды следующим образом: Предположим, что уровень воды h , и мы хотим добавить 1 сантиметр воды. Мы назовем шестиугольники высотой h или меньше, те, которые собираются (или уже находятся) под водой, « погружены ». Вода будет проливаться через любой затонувший шестиугольник, который не окружен шестью соседями. Мы устраняем все такие шестиугольники; Конечно, теперь у некоторых других затонувших шестиугольников может быть меньше шести соседей, и их также необходимо устранить. Мы продолжаем в том же духе до сходимости, то есть до тех пор, пока все оставшиеся затопленные шестиугольники не будут иметь ровно шесть соседей. В этот момент мы добавляем количество погруженных шестиугольников (полученный объем воды) к общему количеству и увеличиваем уровень воды.

В конце концов, все шестиугольники будут уничтожены, и мы остановимся.

Рубин 299

f=->i{s={}
l=i.lines
y=0
l.map{|r|x=0
r.scan(/../){s[[x,y]]=[v=$&.to_i,v<1?0:99];x+=1}
y+=1}
loop{break if s.map{|c,r|x,y=c
m = [[-1,-1],[1,-1],[-2,0],[2,0],[1,-1],[1,1]].map{|w,z|s[[x+w,y+z]]}.map{|n|n ?n[0]+n[1]:0}.min
r[1]=[0,m-r[0]].max if r[0]+r[1]>m&&r[1]>0}.none?}
s.map{|c,r|r[1]}.reduce :+}

Краткое описание алгоритма:

• анализирует входные данные и для каждого стержня сохраняет массив из двух элементов вида [rod_height, water_height]
• стержни помещаются в хеш и индексируются по их координатам x, y
• протекающая часть воды учитывает высоту стержня / воды ближайших соседей

Чуть более читаемая версия доступна здесь: http://ideone.com/cWkamV

Запустите онлайн версию с тестами: http://ideone.com/3SFjPN