Wprowadzenie

Niech pole będzie prostokątem wypełnionym tylko znakami -i [0-9]. Przykładem pola jest:

11-011123
111-010--
0010---01
111-01234

Widzisz, że to pole zostało podzielone na trzy mniejsze obszary:

Aby obliczyć wynik mniejszego obszaru, po prostu dodajemy wszystkie liczby. Na przykład:

11
111
0010
111

1 + 1 + 1 + 1 + 1 + 0 + 0 + 1 + 0 + 1 + 1 + 1 = 9

Całkowity wynik dla tego obszaru to 9 . Robimy teraz to samo dla drugiego obszaru:

   011123
    010

0 + 1 + 1 + 1 + 2 + 3 + 0 + 1 + 0 = 9

Łączny wynik to także 9 . Teraz musimy zbadać ostatni obszar:

       01
    01234

0 + 1 + 0 + 1 + 2 + 3 + 4 = 11

Ma to łączny wynik 11 . Najwyższy wynik na boisku to 11, więc tego potrzebujemy.

Zadanie

Biorąc pod uwagę pole (w postaci ciągu 2D, tablicy itp.), Wypisz najwyższy wynik na polu. Możesz założyć, że podane pola zawsze będą zawierać co najmniej 1 cyfrę. To jest golf golfowy , więc wygrywanie z najmniejszą ilością bajtów wygrywa!

Przypadki testowe

Przypadek testowy 1:

Input:
1

Output:
1

Przypadek testowy 2:

Input:
1-1-1-1
-1-1-1-
2-1-1-1
-1-1-1-

Output:
2

Przypadek testowy 3:

Input:
12-45-
4-65-9
87-654
12-487
45----
684764

Output:
69

Przypadek testowy 4:

Input:
111-12
------
21--10

Output:
3

MATL , 54 51 49 bajtów

n:"G~1@(2Y6Z+leG45>1e*5M@)*]vtz:"otY*g]G48-X:*sX>

Dane wejściowe to tablica znaków 2D w formacie MATL (AB), z ;separatorem wierszy. Dane wejściowe w przykładzie i przypadkach testowych wynoszą odpowiednio:

['11-011123';'111-010--';'0010---01';'111-01234']
['1']
['1-1-1-1';'-1-1-1-';'2-1-1-1';'-1-1-1-']
['12-45-';'4-65-9';'87-654';'12-487';'45----';'684764']
['111-12';'------';'21--10']

Wypróbuj online!

Wyjaśnienie

Działa to poprzez zbudowanie macierzy przyległości wykresu zdefiniowanej przez relację „bycie połączonym”. Jako przykład rozważ pole 3 × 4

52-4
15-8
3-72

Wpisy w tablicy 2D można łatwo opisać w MATL, stosując indeksowanie liniowe (główne kolumny). W przypadku 3 × 4 indeks liniowy każdego wpisu podaje się jako

1  4  7 10
2  5  8 11
3  6  9 12

Macierz przylegania jest budowana etapami przy użyciu mnożenia macierzy. W pierwszym etapie rozważani są najbliżsi sąsiedzi. Na przykład punkt o indeksie 3 jest sąsiadem samego siebie i tego o indeksie 2. Nie jest sąsiadem liczby 6, ponieważ punkt ten nie zawiera liczby zgodnej z polem. W tym przykładzie macierzą przyległości relacji „najbliższy sąsiad” jest macierz L 12 × 12 podana jako

1 1 0 1 0 0 0 0 0 0 0 0
1 1 1 0 1 0 0 0 0 0 0 0
0 1 1 0 0 0 0 0 0 0 0 0
1 0 0 1 1 0 0 0 0 0 0 0
0 1 0 1 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 0 0 1
0 0 0 0 0 0 0 0 0 1 1 0
0 0 0 0 0 0 0 0 0 1 1 1
0 0 0 0 0 0 0 0 1 0 1 1

(Widać, że kolumna 3 ma wartość 1w wierszach 2 i 3.) Ta macierz jest zawsze symetryczna, a jej przekątna ma wartość 1dla punktów, które nie zawierają -.

Następnym krokiem byłaby macierz przyległości relacji „połączonej co najwyżej z jednym punktem pomiędzy ”. Aby go uzyskać, wystarczy pomnożyć L i ustawić niezerowe wpisy na 1. Zasadniczo macierz przylegania relacji „połączonej jakąś ścieżką”, M , jest uzyskiwana przez podniesienie L do wykładnika wykładniczego (w sensie macierzowym), który reprezentuje maksymalną możliwą długość ścieżki. Górna granica maksymalna długość drogi jest liczba niezerowych w pozycji L .

Bezpośrednie obliczenie mocy macierzy może spowodować przepełnienie, ponieważ szybko pojawiają się duże liczby. Dlatego lepiej jest stopniowo pomnożyć przez tę samą macierz, konwertując niezerowe wpisy na 1 po każdym kroku, aby zapobiec tworzeniu się dużych liczb.

Kolumna I z M oznacza punkty, które są połączone (dowolnym ścieżką) z punktem ı . Teraz pole poziomu można sprowadzić do wektora kolumny c w kolejności liniowej, gdzie każdy wpis zawiera odpowiednią liczbę lub niezdefiniowaną wartość dla -. Więc w tym przypadku byłoby c

5
1
3
2
5
-
-
-
7
4
8
2

Mutantowanie każdej kolumny M przez element c i obliczanie sumy każdej kolumny daje, dla każdego punktu i , całkowity wynik punktu powierzchni i, do którego należy. Obszar jest definiowany przez wszystkie punkty, które są ze sobą połączone. Zauważ, że wiele kolumn da ten sam wynik; mianowicie kolumny i oraz j dadzą tę samą sumę, jeśli punkty i i j są połączone (należą do tego samego obszaru). Ostateczny wynik to maksimum tych sum.

        % Implicitly take input: 2D char array
n:      % Range [1,...,N], where N is number of entries in the input
"       % For loop. Each iteration builds a row of matrix L
  G     %   Push input again
  ~     %   Logical negate: transform into matrix of zeros
  1     %   Push 1, to be written into a matrix entry
  @     %   Iteration index. Ranges from 1 to N
  (     %   Write that 1 into the N-th entry (linear order)
  2Y6   %   Push array [0 1 0; 1 1 1; 0 1 0]: mask of immediate neighbours
  Z+    %   Convolve and keep same-size result
  le    %   Linearize into row array
  G45>  %   Array of same size as the input that contains 1 for numbers, 0 for '-'
  1e    %   Linearize into row array
  *     %   Multiply element-wise
  5M    %   Push last array again: 1 for numbers, 0 for '-'
  @)    %   Get 0 or 1 value of that array corresponding to current iteration
  *     %   Multiply. This is to give a row of zeros for non-numbers
]       % End. We have all rows of L in the stack
v       % Concatenate all rows into a matrix: L.
tz:     % Duplicate. Range [1,...,K], where K is the number of nonzeros in L
"       % For loop. Repear K times. This loop computes the 0/1 matrix power
  o     %   Convert matrix entries to double
  tY*   %   Duplicate and matrix-multiply
  g     %   Convert to logical values, that is, nonzero values become 1
]       % End. We have matrix M
G48-    % Convert input chars to the corresponding numbers by subtractig 48
X:      % Linearize into column array. This is vector c
*       % Element-wise multiplication with broadcast (implicit repetition)
s       % Sum of each column. Gives a row array
X>      % Maximum of that row array
        % Implicitly display

JavaScript (ES6), 157 bajtów

s=>[...o=s].map((n,i)=>o=n<'.'|(a=[...s]).map(_=>a.map((c,j)=>c>'-'&c<10&(a[j+1]|a[j-1]|a[j+l]|a[j-l])>90?a[n-=-c,j]=99:0),a[i]=99)|o>n?o:n,l=~s.search`
`)|o

Wyjaśnienie

Pobiera pole wejściowe jako ciąg. Dla każdej liczby w polu sumuje wszystkie liczby w obszarze. Odbywa się to poprzez wielokrotne iterowanie każdej liczby w polu, dodając liczbę do wyniku, jeśli sąsiadująca komórka zawiera wcześniej zliczoną liczbę. Liczby, które są częścią obszaru są reprezentowane przez ustawienie ich na 99, aby nie były ponownie liczone. Wysyła najwyższy wynik jako liczbę.

var solution =

s=>
  [...o=s].map((n,i)=>o=n<'.'|             // for each number on the field
                                           // n = area score
      (a=[...s])                           // a = array of each field character
      .map(_=>                             // loop to ensure whole area is found
        a.map((c,j)=>                      // for each cell c at index j
          c>'-'&c<10&                      // if the current cell is a number
          (a[j+1]|a[j-1]|a[j+l]|a[j-l])>90 // and an adjacent cells is in the area
          ?a[n-=-c,j]=99:0                 // add the cell to the area
        ),                                 // and the number to the score
        a[i]=99                            // mark the starting cell as counted
      )
      |o>n?o:n,                            // o = output (max of o and n)
    l=~s.search`
`                                          // l = line length of field
  )
  |o                                       // return o

<textarea id="input" rows="6" cols="40">12-45-
4-65-9
87-654
12-487
45----
684764</textarea><br />
<button onclick="result.textContent=solution(input.value)">Go</button>
<pre id="result"></pre>

Pyth, 93 bajty

A,hlh.zjJ\-.zKsm?qdJd\#HD'b=KXKbJR+i@HbTsm?&&gd0<dlKq@Kd\#'d0[tbhb-bG+bG;Wh=NxK\#=+Y'N)h.MZY

Wypróbuj online!

Jak to działa

Pierwszy krok: przeczytaj dane wejściowe

A,hlh.zjJ\-.zKsm?qdJd\#H
A,                           Assign the following to G and H:
  hlh.z                          G = increment(length(first(all_input())))
       jJ\-.z                    H = join(J="-",all_input())
                m       H    for d in H:
                 ?qdJ            if equal(d,J):
                     d               add d to the list
                                 else:
                      \#             add "#" to the list
                             end
               s             sum the list
              K              assign to K

Sample input:
11-011123
111-010--
0010---01
111-01234

G = 10
H = "11-011123-111-010---0010---01-111-01234" (note the extra dashes connecting each line)
J = "-"
K = "##-######-###-###---####---##-###-#####"

Drugi krok: zdefiniuj funkcję do oceny jednego obszaru

D'b=KXKbJR+i@HbTsm?&&gd0<dlKq@Kd\#'d0[tbhb-bG+bG;
D'b                                             ;  def quote(b):
   =KXKbJ                                              K[b] = J
         R+                                            return the sum of A and B, where:
           i@HbT                                         A = to_integer(H[b],10)

                 m                   [tbhb-bG+bG         for d in {dec(b), inc(b), minus(b,G), add(b,G)}:
                  ?&&                                      if .... and ........ and ............... :
                     gd0                                      d>=0
                        <dlK                                           d<len(K)
                            q@Kd\#                                                  equal(K[d],"#")
                                  'd                           add quote(d) to temp_list
                                                           else:
                                    0                          add 0 to temp_list
                s                                        B = sum(temp_list)

Basically, this function (quote) is given a starting
point (b), and then recursively find its neighbour and
add their values to the output.

Trzeci krok: przeczytaj wszystkie obszary i znajdź wymagane maksimum

Wh=NxK\#=+Y'N)h.MZY
Wh=NxK\#     )         while inc(N=find(K,"#")):   --while K still has "#"
        =+Y'N              Y+= quote(N)
               .MZY    find the maximum of Y,
              h        then print the first.