Trouver un rectangle maximal de 1s

21

Contexte

Je veux acheter un terrain et y construire ma maison. Ma maison doit être rectangulaire et aussi grande que possible; cependant, les parcelles disponibles ont beaucoup de zones rocheuses sur lesquelles je ne peux pas construire, et j'ai du mal à installer une maison potentielle sur les parcelles. Je veux que vous écriviez un programme qui analyse les parcelles pour moi.

Entrée et sortie

Votre entrée est un tableau 2D rectangulaire de bits, de taille au moins 1 × 1, dans n'importe quel format raisonnable. Le tableau représente une parcelle de terrain; 1s sont de "bonnes" zones où je pourrais construire ma maison, et 0s sont des zones "rocheuses" où la maison ne peut pas être construite.

Votre sortie doit être l'aire maximale d'un rectangle plein de 1s dans le tableau d'entrée. Il représente la superficie de la plus grande maison que j'ai pu construire sur le terrain. Notez que s'il n'y a pas de 1s dans l'entrée, alors la sortie l'est 0.

Exemple

Considérez l'entrée

101
011
111

Le plus grand rectangle de 1s est le rectangle 2 × 2 dans le coin inférieur droit. Cela signifie que la sortie correcte est 4.

Règles et notation

Vous pouvez écrire un programme complet ou une fonction. Le nombre d'octets le plus bas l'emporte et les failles standard sont interdites.

Cas de test

0
-> 0

1
-> 1

00
00
-> 0

01
10
-> 1

01
11
-> 2

111
010
111
-> 3

101
011
111
-> 4

0111
1110
1100
-> 4

1111111
1110111
1011101
-> 7

111011000
110111100
001111110
011111111
001111110
000111100
000011000
-> 20

000110000
110110010
110111110
110011100
010011111
111111111
111101110
-> 12
Zgarb
la source
8
Bulldozer, 4 octets: plow.
Conor O'Brien
1
Est-ce correct si ma solution ne fonctionne que pour des rectangles jusqu'à 30 × 30?
Neil
1
@Neil Non, cela devrait (au moins théoriquement) fonctionner pour des entrées aussi importantes que votre langue peut les gérer.
Zgarb
1
J'espérais faire un peu de tweakling sournois mais dans ce cas, je ne m'embêterai pas.
Neil
1
La solution doit-elle tenir compte de la rotation?

Réponses:

13

Gelée , 21 20 18 17 octets

ṡṂ€€×"
‘×¥\ç"Ụ€FṀ

Essayez-le en ligne! ou vérifiez tous les cas de test .

Contexte

Soit M une matrice de bits telle que

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

Nous commençons par compter le nombre de 1 bits dans chaque colonne de M , en réinitialisant le compte chaque fois que nous rencontrons un bit de 0 .

Pour notre exemple de matrice, cela donne

0 0 0 1 1 0 0 0 0
1 1 0 2 2 0 0 1 0
2 2 0 3 3 1 1 2 0
3 3 0 0 4 2 2 0 0
0 4 0 0 5 3 3 1 1
1 5 1 1 6 4 4 2 2
2 6 2 2 0 5 5 3 0

Ensuite, nous calculons toutes les sous-listes contiguës de chaque ligne. Nous y parvenons en générant toutes les tranches de longueur k , où k varie entre 1 et le nombre d'entrées dans chaque ligne.

Pour l'avant-dernière ligne, cela donne

[1], [5], [1], [1], [6], [4], [4], [2], [2]
[1, 5], [5, 1], [1, 1], [1, 6], [6, 4], [4, 4], [4, 2], [2, 2]
[1, 5, 1], [5, 1, 1], [1, 1, 6], [1, 6, 4], [6, 4, 4], [4, 4, 2], [4, 2, 2]
[1, 5, 1, 1], [5, 1, 1, 6], [1, 1, 6, 4], [1, 6, 4, 4], [6, 4, 4, 2], [4, 4, 2, 2]
[1, 5, 1, 1, 6], [5, 1, 1, 6, 4], [1, 1, 6, 4, 4], [1, 6, 4, 4, 2], [6, 4, 4, 2, 2]
[1, 5, 1, 1, 6, 4], [5, 1, 1, 6, 4, 4], [1, 1, 6, 4, 4, 2], [1, 6, 4, 4, 2, 2]
[1, 5, 1, 1, 6, 4, 4], [5, 1, 1, 6, 4, 4, 2], [1, 1, 6, 4, 4, 2, 2]
[1, 5, 1, 1, 6, 4, 4, 2], [5, 1, 1, 6, 4, 4, 2, 2]
[1, 5, 1, 1, 6, 4, 4, 2, 2]

Ensuite, nous mappons chaque tranche sur le produit de son minimum et de sa longueur. Pour chaque tranche, cela calcule l'aire du rectangle de 1 bits de hauteur maximale qui a la tranche donnée comme ligne du bas.

Pour les tranches de longueur 3 de l'avant-dernière ligne de notre exemple de matrice, cela donne

3 3 3 3 12 6 6

Il ne reste plus qu'à prendre le maximum sur toutes les tranches de toutes les lignes.

Pour notre exemple de matrice, cela donne 12 .

Comment ça marche

‘×¥\ç"Ụ€FṀ  Main link. Argument: M (2D list of bits)

   \        Reduce the columns of M by the link to the left.
  ¥           Combine the two atoms to the left into a dyadic chain.
‘               Increment the left argument.
 ×              Multiply the result with the right argument.
      Ụ€    Grade up each; yield the indices of each row of M, sorted by their
            values. The order is not important here; we just need the indices.
    ç"      Apply the helper link to each element of the result to the left and
            the corresponding element of the result to the right.
        F   Flatten the resulting, nested list.
         Ṁ  Extract the maximum.


ṡṂ€€×"      Helper link. Arguments: R (row), X (indices of R)

ṡ           For each k in X, split R into overlapping slices of length k.
 Ṁ€€        Compute the minimum of each individual slice.
    ×"      Multiply the minima of all slices of length k by k.
Dennis
la source
7
Je ne savais pas où était ce riche, Dennis. € $ €€€
orlp
5
Tout est à propos de l'argent. L'échange de $ contre ¥ a permis d'économiser 2 octets.
Dennis
1
Comment diable trouvez-vous toujours des approches intelligentes comme celle-ci?
Leaky Nun
Parce que l'on ne se contente pas de devancer Dennis!
Gryphon - Rétablir Monica le
6

MATL, 32 31 27 octets

n:"@:"@1M2$ltntG4$bZ+=a*vX>

Cela utilise une approche basée sur la convolution 2D par force brute. Toutes les tailles de rectangle possibles sont créées et convolutées avec le terrain. Le résultat maximum de toutes les circonvolutions est la zone de rectangle maximale.

C'est une solution extrêmement inefficace car pour économiser des octets, je crée des noyaux pour tous les rectangles entre [1, 1]et [numel(input) numel(input)]plutôt que de déterminer réellement le nombre de lignes / colonnes dans l'entrée pour déterminer les plages de dimensions de rectangle appropriées.

Merci à @Luis d'avoir suggéré l'utilisation Met omis le ]].

Essayez-le en ligne!

Explication

        % Implicitly grab input as a 2D numeric array
n       % Compute the number of elements in the input (over estimation of max kernel size)
:       % Create array 1:n
"       % For each value
  @     % Current loop index
  :     % Create an array from 1:(current_index)
  "     % For each of these values   
    @   % Push the current index onto the stack
    1M  % Grab the input to the previous function call (the outer index)
    2$l % Create an array of 1's whose dimensions are specified by top two stack elements
    tn  % Duplicate this array and compute number of elements
    t   % Duplicate this number
    G   % Explicitly grab input
    4$b % Bubble up the 4th element from the stack (the kernel)
    Z+  % Perform 2D convolution of this kernel and the input
    =a  % Determine if any convolution result (in each column) is equal to the area of the kernel.
        % This yields a row vector
    *   % Multiply the logical result by the area
    v   % Vertically concatenate all results (forces the row vectors above to be column vectors)
    X>  % Compute the maximum yielding the largest area
        % Implicitly display the result.
Suever
la source
5

Julia, 83 60 57 53 octets

!M=M1?sum(M):maximum(t->!rotr90(M,t)[2:end,:],0:3)

Essayez-le en ligne! Le dernier cas de test dépasse le délai de TIO, mais je l'ai vérifié localement.

Comment ça marche

Tout d'abord ! vérifie si son argument de matrice M est entièrement composé de 1 .

  • Si oui ,! renvoie la somme des entrées de M , qui est égale à sa surface.

  • Sinon ,! fait ce qui suit:

    1. Tournez M de 0 ° , 90 ° , 180 ° et 270 ° dans le sens horaire.

    2. Retirer la première ligne de chacune des quatre rotations, éliminant efficacement une de rangée supérieure, rangée du bas, colonne de gauche et la colonne droite de M .

    3. Appelez-vous récursivement sur chacune des sous-matrices.

    4. Renvoie le maximum des valeurs de retour des appels récursifs.

Dennis
la source
4

JavaScript (ES6), 97 octets

a=>a.map((b,i)=>a.slice(i).map((c,j)=>c.map((d,k)=>(n=(b[k]&=d)&&n+j+1)>r?r=n:0,n=0),c=[]),r=0)|r

Il s'avère que le twiddling peu gagne toujours. Accepte un tableau de tableau d'entiers. Non golfé:

function rect(array) {
    var max = 0;
    for (var i = 0; i < array.length; i++) {
        var bits = array[i];
        for (var j = 0; i + j < array.length;) {
            var row = array[i + j];
            j++;
            var size = 0;
            for (var k = 0; k < row.length; k++) {
                if (!row[k]) bits[k] = 0;
                size = ones[k] ? size + j : 0;
                if (size > max) max = size;
            }
        }
    }
    return max;
}

Le tableau est découpé en lignes selon les autres réponses, de sorte que chaque plage possible de lignes est bouclée. Étant donné une plage de lignes, l'étape suivante consiste à mesurer les rectangles disponibles. Ceci est réalisé en ANDant les lignes ensemble au niveau du bit; le résultat est une liste de bits qui ont été définis dans toute la plage de lignes. Il reste alors à trouver la longueur maximale des bits définis dans la ligne et à la multiplier par la hauteur de la plage. Test sans vergogne volé à @ ed65:

f=
a=>a.map((b,i)=>a.slice(i).map((c,j)=>c.map((d,k)=>(n=(b[k]&=d)&&n+j+1)>r?r=n:0,n=0),c=[]),r=0)|r

// test cases as strings, converted to 2d arrays
result.textContent = [
  ['0', 0],
  ['1', 1], 
  ['00 00', 0],
  ['01 10', 1],
  ['01 11', 2],
  ['111 010 111', 3],
  ['101 011 111', 4],
  ['0111 1110 1100', 4],
  ['1111111 1110111 1011101', 7],
  ['111011000 110111100 001111110 011111111 001111110 000111100 000011000', 20],
  ['000110000 110110010 110111110 110011100 010011111 111111111 111101110', 12]
].map(t => t[0].replace(/ /g, '\n') + '\n' + t[1] + '\n' + f(t[0].split` `.map(r => [...r]))).join`\n\n`
<pre id=result></pre>

Neil
la source
1
Je voterais positivement, mais comme votre réputation est exactement 10000000000000 en binaire, je pense que je vais le laisser un peu.
Level River St
im à tour de rôle pour le gâcher: D, une idée similaire m'est venue à l'esprit mais j'ai l'
habitude
4

Python 2.7, 93 91 89 81 79 octets

f=lambda M,t=1:max(f(M[1:]),f(zip(*M)[::-1],t+1))if`t/3`in`M`else`M`.count(`t`)

L'entrée est une liste de tuples. Vérifiez les plus petits cas de test ici et les plus grands cas de test ici .

Sans mémorisation, les deux derniers cas de test dépassent le délai d'Ideone, car ils nécessitent respectivement 1 530 831 935 et 2 848 806 121 appels vers f , ce qui prend 39 et 72 minutes sur ma machine.

Algorithme

Pour une matrice M donnée , l'idée générale est d'itérer sur toutes les sous-matrices de M en supprimant les rangées supérieures et en faisant tourner les quarts de tour dans le sens antihoraire, en gardant une trace des tailles des sous-matrices rencontrées qui se composent entièrement de 1 bit.

Jouer une implémentation récursive simple de l'idée ci-dessus conduit à une fonction f (M) qui fait ce qui suit.

  1. Si M ne contient aucun 0 bit, retourne son nombre de 1 bit.

  2. Si nous avons pivotée M deux fois déjà et il ne contient pas de 1 bits retour 0 .

  3. Si nous avons déjà tourné M cinq fois, retournez 0 .

  4. Appeler récursivement f sur M sans sa ligne supérieure.

  5. Appeler récursivement f sur M tourné d'un quart de tour dans le sens antihoraire.

  6. Renvoie le maximum des valeurs de retour des appels récursifs.

Code

Dans l'implémentation, nous utilisons un argument de fonction supplémentaire t par défaut à 1 pour garder une trace du nombre de fois où nous avons déjà tourné cette matrice particulière. Cela permet de condenser les étapes 1 à 3 en une seule étape en testant ​`t/3`in`M`​et en retournant ​`M`.count(`t`)​si le test échoue.

  1. Si t = 1 , nous n'avons pas fait tourner cette sous-matrice particulière précédemment dans cette branche.

    t / 3 = 0 , donc ​`t/3`in`M`​retournera True si la représentation sous forme de chaîne de M contient le caractère 0 .

    Si elle n'a pas, nous reviendrons ​`M`.count(`t`)​, le nombre de fois que le caractère 1 apparaît dans la représentation de chaîne de M .

    Notez qu'une matrice sans 0 bit ne peut apparaître que si t = 1 , puisque nous ne récurrons pas dans ce cas.

  2. Si 3 ≤ t ≤ 5 , nous avons précédemment tourné cette sous-matrice particulière au moins deux fois dans cette branche.

    t / 3 = 1 , donc ​`t/3`in`M`​retournera True si la représentation sous forme de chaîne de M contient le caractère 1 .

    Si elle ne le fait pas, nous revenons 0 calculé comme ​`M`.count(`t`)​le nombre de fois la représentation de chaîne de t ( par exemple, le caractère 3 , 4 ou 5 ) apparaît dans la représentation de chaîne de M .

  3. Si t = 6 , nous avons précédemment tourné cette sous-matrice particulière cinq fois dans cette branche.

    t / 3 = 2 , ​`t/3`in`M`​renvoie donc False , car la représentation sous forme de chaîne de M ne contient pas le caractère 2 .

    Nous revenons 0 calculé comme ​`M`.count(`t`)​, le nombre de fois que le caractère 6 apparaît dans la représentation de chaîne de M .

Si f n'est pas déjà retourné, les étapes restantes sont exécutées.

  1. f(M[1:])appelle f sur M sans sa ligne supérieure. Puisque t n'est pas spécifié, il vaut 1 par défaut , signalant que c'est la première fois que f rencontre cette sous-matrice particulière dans cette branche.

  2. f(zip(*M)[::-1],t+1)les appels f sur M ont tourné d'un quart de tour dans le sens antihoraire, incrémentant t pour garder une trace du temps pendant lequel nous avons fait tourner cette sous-matrice particulière dans cette branche.

    Le quart de tour est obtenue par zipping les rangées de M avec l'autre, le retour tuples des éléments de concordance M rangées d », ainsi transposant M , puis en inversant l'ordre des lignes ( par exemple, en plaçant la ligne de haut en bas et vice - versa ).

  3. maxRetourne enfin le maximum des valeurs de retour des appels récursifs.

Dennis
la source
hmm toutes ces soumissions sont des idées distinguées? assez fascinant, que fait la fonction zip?
Abr001am
ziprenvoie une liste de tuples des éléments correspondants de ses arguments. Avec une liste 2D non matricielle (matrice) *M, il transpose essentiellement les lignes et les colonnes, zip(*M[::-1])effectue donc une rotation de 90 ° dans le sens horaire.
Dennis
thx, le python est un charme, je l'apprendrai un jour.
Abr001
2

JavaScript (ES6), 154 176

Edit a essayé de raccourcir un peu, mais ne peut pas rivaliser avec la solution de @ Neil

Essayez tous les rectangles possibles, renvoyez la taille maximale. Probablement le même algorithme de la réponse Matl, juste 6 fois plus longtemps.
Entrée sous forme de tableau 2d d'entiers

g=>g.map((r,i)=>r.map((x,j)=>v=s(r,j,(_,l)=>s(g,i,(_,k)=>!s(g,k,r=>s(r,l,x=>!x,l+j+1),k+i+1)))&(t=-~i*-~j)>v?t:v),s=(a,i,l,j)=>a.slice(i,j).some(l),v=0)|v

Moins golfé

Ceci est l'algorithme d'origine, la version golfée abuse de beaucoup de fonctions de traversée de tableau au lieu des boucles for

g=>{
  v = 0
  for(i = h = g.length; i; i--)
    for(j = w = g[0].length; j; j--)
    {
      p = true
      for(k=0; p && k <= h-i; k++)
        for(l=0; p && l <= w-j; j++)
          p = g.slice(k, k+i).some(r=>r.slice(l, l+j).some(x=>!x));
      if (!p && i*j<v)
        v = i*j
    }
  return v
}

Tester

f=g=>g.map((r,i)=>r.map((x,j)=>v=s(r,j,(_,l)=>s(g,i,(_,k)=>!s(g,k,r=>s(r,l,x=>!x,l+j+1),k+i+1)))&(t=-~i*-~j)>v?t:v),s=(a,i,l,j)=>a.slice(i,j).some(l),v=0)|v

console.log=(...x)=>O.textContent+=x+'\n'

// test cases as strings, converted to 2d arrays
;[
  ['0',0],['1',1],['00 00',0],['01 10',1],['01 11',2],
  ['111 010 111',3],['101 011 111',4],
  ['0111 1110 1100',4],['1111111 1110111 1011101',7],
  ['111011000 110111100 001111110 011111111 001111110 000111100 000011000',20],
  ['000110000 110110010 110111110 110011100 010011111 111111111 111101110',12]
].forEach(t=>{
  var k=t[1]
  var p=t[0].split` `.map(r=>[...r].map(x=>+x))
  var r=f(p)
  console.log((r==k?'OK':'KO')+' '+r+(r==k?'':' expected '+k)+'\n'+p.join`\n`+'\n')
  })
<pre id=O></pre>

edc65
la source
2

APL (Dyalog Extended) , 27 23 20 octets

-3 octets par Adám et ngn

{⌈/∊(×/×⍵⍷⍨⍴∘1)¨⍳⍴⍵}

Essayez-le en ligne!

{⌈/∊(×/×⍵⍷⍨⍴∘1)¨⍳⍴⍵}    Monadic function taking an argument ⍵:
                 ⍳⍴⍵     Indices: e.g. for a 3x7 array
                                       (1 1) (1 2) ...  (1 7)
                                       (2 1) (2 2)  ... (2 7)
                                       (3 1) (3 2)  ... (3 7)
    (×/×⍵⍷⍨⍴∘1)         Helper fn: Takes  and x (e.g. (2 2))
            ⍴∘1             Make an array of 1s of shape x. Call it a.
        ⍵⍷⍨                 All places where a exists in x
     ×/                      Product of x's dims (size of a)
       ×                 Size of a where a is in ⍵, and 0 elsewhere.
    (×/×⍵⍷⍨⍴∘1)¨        Call the helper function on x and each (¨) index.
                            We now have a nested list containing sizes of blocks in ⍵
                            and many 0s.
   ∊                        Flatten
 ⌈/                        Find the maximum value.
lirtosiast
la source
{⌈/,(×/×1∊⍵⍷⍨⍴∘1)¨⍳⍴⍵}est plus court et plus simple (ne nécessite même pas Extended).
Adám
1
@lirtosiast @ Adám{⌈/∊(×/×⍵⍷⍨⍴∘1)¨⍳⍴⍵}
ngn
2

Brachylog , 20 17 15 octets

Merci à Kroppeb pour 2 octets

{s\sc≡ᵛ¹l}ᶠ⌉|hh

Essayez-le en ligne!

Explication

{        }ᶠ      Find all possible outputs of the following predicate:
 s                Find a sublist of the array (i.e. remove 0 or more rows from the top
                  and/or bottom)
  \               Transpose the array
   s              Find a sublist again
                  The result is some sub-rectangle of the array
    c             Concatenate all the rows in that rectangle into one list
     ≡ᵛ¹          Verify that all the elements are 1
        l         Get the length (i.e. how many 1's make up the rectangle)
                 Now we have a list of the sizes of all possible 1-rectangles
           ⌉     Take the maximum

            |    If no 1-rectangles could be found:
             hh   Take the head of the head of the array (i.e. the top left element)
                 Since the array contains no 1's in this case, this will give 0
DLosc
la source
aapeut être remplacé par s Essayez-le en ligne!
Kroppeb
1

R , 129 122 octets

function(M,D=dim(M),L=`for`){L(i,1:D,L(j,1:D[2],L(r,0:(D-i),L(c,0:(D[2]-j),F<-max(F,i*j*(i*j==sum(M[r+1:i,c+1:j])))))))
F}

Essayez-le en ligne!

Approche brute et simple de la force brute.

Code déroulé et explication:

function(M){                       # M is the matrix of 0/1
n = 0                              # n is the biggest rectangle found
R=nrow(M)
C=ncol(M)
for(i in 1:R)                      # for each possible num of rows of the rectangle
  for(j in 1:C)                    # for each possible num of cols of the rectangle
    for(r in 0:(R-i))              # for each possible position offset on the rows
      for(c in 0:(C-j){            # for each possible position offset on the cols

         subM = M[1:i+r,1:j+c]     # sub-set the matrix given the size of rectangle and offsets

         if(sum(subM)==i*j)        # if sub-matrix is full of 1's
            rec = i*j              # (i.e. nrow*ncol == sum of values in sub-matrix)
         else                      # store the rectangle area
            rec = 0                # otherwise store 0

         n = max(n,rec)            # keep the maximum rectangle found
      }
}
digEmAll
la source
0

Matlab 106 octets

x=input('');[n,k]=size(x);r=0;for p=1:n;for m=1:k;r=max([p*m*(any(conv2(x,ones(p,m))==p*m)),r]);end;end;r

Non golfé:

x=input(''); %//Take input
[n,k]=size(x); %//Determine array size
r=0; %//Variable for output. Initially zero
for p=1:n; %// Loop through the columns
    for m=1:k; %// Loop through the rows
        r=max([p*m*(any(conv2(x,ones(p,m))==p*m)),r]);%//See explanation below
    end;
end;
r %//Display result

L'opération dans la boucle commence par une convolution 2D conv2()du tableau d'entrée avec le p*mtableau de ceux-ci. ==p*mvérifie si le tableau résultant contient un élément égal à p*m. L'élément correspondant est tourné vers 1, tous les autres éléments sont tournés vers 0. any()transforme le tableau en vecteur. 1Sinon, les colonnes contenant au moins une entrée différente de zéro sont converties 0. p*m*()multiplie le vecteur en p*mtransformant ainsi tous les 1-s en p*m. [__,r]les crochets concaténent le résultat obtenu avec la zone maximale précédente stockée dans r. Enfin, max()trouve la valeur maximale dans le vecteur résultant.

brainkz
la source
que fait la fonction?
Abr001
@ Agawa001 pour chaque colonne du tableau 2D any()renvoie 1si la colonne contient un élément différent de zéro et 0sinon.
brainkz
0

Matlab (222)(209)

En fait, cette solution me fait honte d'être deux fois la vraie solution dans la même langue mais ... blimey, j'y pensais depuis 6 heures! et l'astuce est une construction légèrement différente des réponses de Dennis et Neil.

    function p=g(x,a,u,i,j),i=i+~u;j=j+u;p=0;if(j*u+i*~u>=size(a,2-u))return;end,x=circshift(x,[0-u -1+u]),a=(x+a).*~~x.*~~a;for h=0+u:1,p=max([p,reshape(a(1:end-j,1:end-i),1,[]),g(~u*(a*h+x*~h)+u*x,a,h,i,j)]);end
  • La fonction est appelée comme

    y=[1 1 1 0 1 1 0 0 0;
    1 1 0 1 1 1 1 0 0;
    0 0 1 1 1 1 1 1 0;
    0 1 1 1 1 1 1 1 1;
    0 0 1 1 1 1 1 1 0;];
    t=g(y,y,[],0,0,0);t,
    
  • Je pourrais économiser plus d'octets si la longueur de la matrice était introduite dans les dimensions de la fonction, même si plus de golf était en cours.

  • Comment cela se passe-t-il?

    Cet algorithme ajoute la matrice réelle à elle-même décalée de celle-ci vers la gauche, avec un peu de twiddling (&). à n'importe quel stade, la matrice résultante est définie comme initiale et ajoutée à elle-même, décalée vers le haut à plusieurs reprises, puis recroquevillée depuis le début avec la nouvelle matrice. Tous les sous-éléments de toutes les matrices générées par cette opération (original_matrix+shifted_matrix)&shifted_and_original_matrices)sont maximisés en sortie.

exemple:

     1 1 1         1 1 0                      2 2 0                  0 2 0                        0 4 0
 M0= 0 1 1  M0<<1= 1 1 0  M1=(M0+M0<<1)&both= 0 2 0    shift(M1,up)= 2 0 0  M2=(M1+sh(M1,u)&both= 0 0 0  
     1 1 0         1 0 0                      2 0 0                  0 0 0                        0 0 0
                        2 0 0                               4 0 0
 M3=(M0<<1+M0<<2)&both= 2 0 0 , M4=(M3+shift(M3,up))&both=  0 0 0
                        0 0 0                               0 0 0

                3 0 0                             
 M5=(M1+M0<<2)= 0 0 0 , M6=(M5+shift(M5,up))&both=zeros(3,3).
                0 0 0

 Max_of_all_values=Max(0,1,2,3,4)=4
Abr001am
la source
0

Japt , 30 octets

®åÏ*°X}ÃÕ®£ZãYÄÃm®rm *Zl}Ãc rw

Essayez tous les cas de test

Environ un port de Dennis's Jelly répond. Les cas de test sont simplement des tableaux 2D de nombres, convertis à partir du format de la question en utilisant ceci .

Explication:

®      Ã                          #For each row:
 å    }                           # Replace each number with this running total:
    °X                            #  Increment the previous total
  Ï*                              #  Multiply it by the current number
        Õ                         #Transpose rows and columns
         ®               Ã        #For each column:
          £    Ã                  # Iterate over the range [0..length) as Y:
           ZãYÄ                   #  Get the subsections of that column with length Y+1
                m®      }         # For each subsection:
                  rm              #  Get the minimum
                     *Zl          #  Multiply it by the length
                          c       #Flatten everything to a single list of possible rectangle sizes
                            rw    #Get the maximum
Kamil Drakari
la source
0

J , 38 octets

,"0/&(1+i.)/@$>./@,@:((#**/)@,;._3"$)]

Essayez-le en ligne!

Comment

,"0/&(1 + i.)/@$ >./@,@:((# * */)@,;._3"$) ]
              @$                             NB. pass the shape of
                                             NB. the input (rows, cols)
                                             NB. to...
,"0/&(1 + i.)/                               NB. this verb, which will
    &(1 + i.)/                               NB. will first create 2
                                             NB. lists: 1...num rows
                                             NB. and 1...num cols.
,"0/                                         NB. and then creat a cross
                                             NB. of every possible 
                                             NB. concatenation of the two,
                                             NB. giving us all possible 
                                             NB. rectangle sizes. pass 
                                             NB. that and...
                                           ] NB. the original input
                 >./@,@:((# * */)@,;._3"$)   NB. to this verb, which
                                   ;._3"$    NB. will take every 
                                             NB. possible rectangle of
                                             NB. every size,
                                 @,          NB. flatten it and...
                         (# * */)            NB. multiply the size of
                                             NB. the list by the list's 
                                             NB. product, yielding the
                                             NB. size of the list if it's
                                             NB. all ones, zero otherwise.
                     ,@:                     NB. Flatten all those results
                                             NB. into one big list
                 >./@                        NB. and take the max.
Jonas
la source