Mam kilka sześciokątnych prętów sklejonych ze sobą w dziwną rzeźbę. Pręty mają od 1 do 99 centymetrów (cm) i 1 cm kwadratowy w przekroju. Wszystkie pręty są przyklejone na sześciokątnej powierzchni do co najmniej jednego innego pręta. Wszystkie pręty są wyrównane na dolnej krawędzi.

Po ulewnym deszczu rzeźba jest pełna wody. Jak dużo wody to trzyma?

Wkład

Twój program powinien wczytać (przez stdin lub plik) kilka wierszy składających się z par spacji i par cyfr określających długość prętów w tym formacie:

  aa  bb
cc  dd  ee
  ff  gg

Każdy pręt (jak tutaj dd) jest przyklejony do maksymalnie 6 otaczających prętów, jak pokazano w przykładach. Brakujące pręty to dziury i nie zbierają wody. Na przykład dane wejściowe

  04  04
04  01  03
  04  04

będzie reprezentować następującą rzeźbę:

Środkowy pręt ma wysokość 1(nie znalazłem dobrego kąta, w którym ten pręt również jest widoczny). Teraz kolumna nad tym prętem może pomieścić 2 cm wody, zanim będzie mogła przelać się nad 3prętem po prawej stronie. Ponieważ żaden z pozostałych prętów może posiadać żadnej wody nad nimi, będzie odpowiedź 2. Oto dwa bardziej złożone przykłady:

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

Wydajność

Twój program powinien wypisać jedną liczbę całkowitą podającą objętość wody w centymetrach sześciennych.

Wynik

Twój wynik to liczba bajtów kodu źródłowego. Najniższe wygrane.

Standardowe luki są jak zwykle zabronione.

Ta łamigłówka została zainspirowana pytaniem SPOJ .

Python 2, 222 bajty

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

Odczytuje dane wejściowe przez STDIN i zapisuje wynik do STDOUT.

Wyjaśnienie

Zaczynamy od zera i stopniowo zwiększamy poziom wody w następujący sposób: Załóżmy, że poziom wody wynosi h , i chcemy dodać 1 centymetr wody. Będziemy nazywać sześciokąty o wysokości h lub mniejszej, te, które mają zamiar zejść (lub już są) pod wodą, „ zanurzone ”. Woda wyleje się przez każdy zanurzony sześciokąt, który nie jest otoczony przez sześciu sąsiadów. Eliminujemy wszystkie takie sześciokąty; oczywiście teraz niektóre inne zanurzone sześciokąty mogą mieć mniej niż sześciu sąsiadów i należy je również wyeliminować. Kontynuujemy w ten sposób, aż do zbieżności, tj. Dopóki wszystkie pozostałe zanurzone sześciokąty nie będą miały dokładnie sześciu sąsiadów. W tym momencie dodajemy liczbę zanurzonych sześciokątów (uzyskaną objętość wody) do całkowitej liczby i zwiększamy poziom wody.

W końcu wszystkie sześciokąty zostaną wyeliminowane i zatrzymamy się.

Rubin 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 :+}

Krótki opis algorytmu:

• analizuje dane wejściowe i dla każdego pręta zapisuje tablicę dwuelementową o postaci [rod_height, water_height]
• pręty są umieszczane w haszu i indeksowane według ich współrzędnych x, y
• część wyciekająca z wody uwzględnia wysokość pręta / wody bezpośrednich sąsiadów

Nieco bardziej czytelna wersja jest dostępna tutaj: http://ideone.com/cWkamV

Uruchom wersję golfową online z testami: http://ideone.com/3SFjPN