introduction

Soit un champ un rectangle rempli uniquement des caractères -et [0-9]. Un exemple de champ est:

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

Vous voyez que ce champ a été séparé en trois zones plus petites:

Pour calculer le score d'une zone plus petite, nous additionnons simplement tous les nombres. Par exemple:

11
111
0010
111

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

Le score total pour ce domaine est de 9 . Nous faisons maintenant la même chose pour le deuxième domaine:

   011123
    010

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

Le score total est également de 9 . Maintenant, nous devons examiner le dernier domaine:

       01
    01234

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

Cela a un score total de 11 . Le score le plus élevé sur le terrain est de 11, c'est donc ce que nous devons produire.

La tâche

Étant donné un champ (sous la forme d'une chaîne 2D, d'un tableau, etc.), affichez le score le plus élevé sur le champ. Vous pouvez supposer que les champs donnés contiendront toujours au moins 1 chiffre. C'est du code-golf , donc la soumission avec le moins d'octets gagne!

Cas de test

Cas de test 1:

Input:
1

Output:
1

Cas de test 2:

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

Output:
2

Cas de test 3:

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

Output:
69

Cas de test 4:

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

Output:
3

MATL , 54 51 49 octets

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

L'entrée est un tableau de caractères 2D au format MATL (AB), avec ;comme séparateur de ligne. Les entrées dans l'exemple et dans les cas de test sont respectivement:

['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']

Essayez-le en ligne!

Explication

Cela fonctionne en construisant une matrice d'adjacence du graphe définie par la relation "étant connecté". Par exemple, considérons le champ 3 × 4

52-4
15-8
3-72

Les entrées dans un tableau 2D sont facilement décrites dans MATL en utilisant l'indexation linéaire (en colonne). Dans le cas 3 × 4, l'indice linéaire de chaque entrée est donné comme

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

La matrice d'adjacence est construite par étapes en utilisant la multiplication matricielle. Dans un premier temps, les voisins immédiats sont pris en compte. Par exemple, le point indexé 3 est voisin de lui-même et de celui d'index 2. Ce n'est pas un voisin de 6 car ce point ne contient pas de nombre selon le champ. Dans cet exemple, la matrice d'adjacence de la relation "voisin immédiat" est la matrice 12 × 12 L donnée comme

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

(On peut voir que la colonne 3 a une valeur 1aux lignes 2 et 3.) Cette matrice est toujours symétrique et sa diagonale a une valeur 1pour les points qui ne contiennent pas -.

L'étape suivante serait la matrice d'adjacence de la relation "connectée avec au plus un point entre les deux ". Pour l'obtenir, il suffit de multiplier L par lui-même et de définir des entrées non nulles sur 1. En général, la matrice d'adjacence de la relation "connecté par un chemin", M , est obtenue en élevant L à un exposant (au sens de la matrice) qui représente la longueur de chemin maximale possible. Une limite supérieure de la longueur de trajet maximale est le nombre d'entrées non nulles dans L .

Le calcul direct de la puissance de la matrice peut provoquer un débordement, car de grands nombres se produisent rapidement. Il est donc préférable de multiplier progressivement par la même matrice, en convertissant les entrées non nulles en 1 après chaque étape pour éviter la formation de grands nombres.

La colonne i de M représente les points qui sont connectés (par n'importe quel chemin) au point i . Maintenant, le champ de niveau peut être réduit à un vecteur de colonne c dans un ordre linéaire, où chaque entrée contient le nombre correspondant ou une valeur indéfinie pour -. Dans ce cas, c serait

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

La multiplication de chaque colonne de M par c élément par élément et le calcul de la somme de chaque colonne donne, pour chaque point i , le score total de la zone à laquelle appartient le point i . Une zone est définie par tous les points qui sont mutuellement connectés. Notez que de nombreuses colonnes donneront le même résultat; à savoir, les colonnes i et j donneront la même somme si les points i et j sont connectés (appartiennent à la même zone). Le résultat final est le maximum de ces sommes.

        % 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 octets

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

Explication

Prend un champ de saisie sous forme de chaîne. Pour chaque numéro du champ, additionne tous les numéros de la zone. Il le fait en itérant plusieurs fois sur chaque numéro du champ, en ajoutant le numéro au score si une cellule adjacente contient un nombre précédemment compté. Les nombres comptés qui font partie de la zone sont représentés en les définissant sur 99 afin qu'ils ne soient pas comptés à nouveau. Produit le score le plus élevé sous forme de nombre.

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 octets

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

Essayez-le en ligne!

Comment ça fonctionne

Première étape: lire l'entrée

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 = "##-######-###-###---####---##-###-#####"

Deuxième étape: définir une fonction pour évaluer une zone

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.

Troisième étape: lire toutes les zones et trouver le maximum requis

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.