Entrada

Quadro: Um contêiner 2D (matriz, lista de listas, etc.) de letras como:

  ["B", "C", "C", "C", "C", "B", "B", "C", "A", "A"],
  ["B", "A", "C", "B", "B", "A", "B", "B", "A", "A"],
  ["B", "C", "B", "C", "A", "A", "A", "B", "C", "B"],
  ["B", "B", "B", "A", "C", "B", "A", "C", "B", "A"],
  ["A", "A", "A", "C", "A", "C", "C", "B", "A", "C"],
  ["A", "B", "B", "A", "A", "C", "B", "C", "C", "C"],
  ["C", "B", "A", "A", "C", "B", "B", "C", "A", "A"]

Se você escolher uma lista de listas, poderá assumir que todas as sublistas têm o mesmo comprimento.

Regras

• Para criar um retângulo válido, você precisa de todos os cantos do retângulo com a mesma 'letra'.
• Exemplo, veja o quadro de amostras com o X abaixo. Você pode ver 'X' em (1,0) também em (4,0) também em (1,3) e em (4,3), então você tem o retângulo [1,0,4,3] que significa de (1,0) a (4,3):

Placa de amostra com X :

  ["B", "X", "C", "C", "X", "B", "B", "C", "A", "A"],
  ["B", "A", "C", "B", "B", "A", "B", "B", "A", "A"],
  ["B", "C", "B", "C", "A", "A", "A", "B", "C", "B"],
  ["B", "X", "B", "A", "X", "B", "A", "C", "B", "A"],
  ["A", "A", "A", "C", "A", "C", "C", "B", "A", "C"],
  ["A", "B", "B", "A", "A", "C", "B", "C", "C", "C"],
  ["C", "B", "A", "A", "C", "B", "B", "C", "A", "A"]

• O objetivo é encontrar o retângulo ou um dos retângulos com a maior área, calculado por (direita-esquerda + 1) * (inferior-superior + 1)
• Se houver vários retângulos com a mesma área máxima, faça a saída de qualquer um. Opcionalmente, aquele com (coordenada superior, coordenada esquerda, coordenada direita, coordenada inferior) lexicograficamente menor.
• Os retângulos devem ter bordas paralelas à borda da placa.
• Cada letra é um caractere ASCII imprimível de A a Z (ambos incluídos).

Saída

A saída deve estar nas posições esquerda e direita dos maiores cantos do retângulo da área. Para a primeira amostra "tabuleiro", o quadrado grande é o amarelo:

E a resposta deve ser:

[1, 1, 8, 4]

Um segundo exemplo de caso de teste

Uma entrada de:

["C", "D", "D", "D", "A", "A"],
["B", "D", "C", "D", "A", "A"],
["B", "D", "D", "C", "A", "C"],
["B", "D", "B", "C", "A", "C"]

Deve produzir uma dessas três listas de coordenadas, identificando uma área de seis retângulos:

[1, 0, 2, 2]
[1, 0, 3, 1]
[3, 2, 5, 3]

Esta pergunta foi publicada no Stack Overflow com o título: Como encontrar o maior retângulo em uma matriz 2D formada por quatro cantos idênticos? e com esta solução JS rude (posso dizer "rude" porque é o meu código;):

Ok, é o meu primeiro post, seja tolerante comigo, por favor. Vou mudar tudo o que você diz para melhorar o teste.

Python 2 , 148 130 bytes

lambda x,e=enumerate:min(((a-c)*(d-b),b,a,d,c)for a,y in e(x)for c,k in e(x)for b,g in e(y)for d,h in e(y)if g==h==k[b]==k[d])[1:]

Experimente online!

Retina , 163 162 bytes

Lw$`(?<=(.*\n)*((.)*))(?=(.))((.)*(?<=(.*))\4)((.*\n)*((?>(?<-3>.)*)(?=\4)(?>(?<-6>.)*))\4)?
$.7,$#1,$.2,-$.($5$#9*$5),$.2,$#1,$.7,$.($#1*_$#9*
4{N`
)m`^.*?,

0G`

Experimente online! Editar: salvou 1 byte porque a )correspondência correspondente à $.(está implícita. Explicação:

Lw$`(?<=(.*\n)*((.)*))(?=(.))((.)*(?<=(.*))\4)((.*\n)*((?>(?<-3>.)*)(?=\4)(?>(?<-6>.)*))\4)?

Essa expressão regular corresponde a retângulos. Os grupos são os seguintes: 1) Linha superior (como contagem de capturas) 2) Coluna esquerda (como comprimento) 3) Balanceamento para garantir o alinhamento dos cantos esquerdos 4) Letra dos cantos 5) Largura + 1 (como comprimento) 6) Balanceamento para garantir o alinhamento dos cantos direitos 7) Coluna direita (como comprimento) 8) não utilizada 9) Altura (como contagem de capturas). A wopção garante que todas as larguras possíveis de retângulos sejam correspondidas para cada canto superior esquerdo. As $opções listam os resultados usando o seguinte padrão de substituição.

$.7,$#1,$.2,-$.($5$#9*$5),$.2,$#1,$.7,$.($#1*_$#9*

As substituições são as seguintes: A coluna da direita, a linha superior, a coluna da esquerda, a negação da área do retângulo (literalmente calculada como o comprimento de repetir a cadeia de largura por um a mais que o número de alturas de vezes), a coluna da esquerda , a linha superior, a coluna da direita, seguida por uma expressão que é avaliada na linha inferior (uma captura custaria 12 bytes, mais as variáveis ​​de um dígito acabaram). As quatro primeiras capturas representam a ordem de classificação em ordem de prioridade. À medida que a Retina classifica de maneira estável, uma classificação de várias colunas pode ser estabelecida, classificando cada coluna de classificação, por sua vez, da menor para a maior prioridade. (A área deve ser classificada em ordem decrescente, para que uma única classificação de sequência não possa ser usada.)

4{N`

Quatro classificações numéricas são então executadas.

)m`^.*?,

A coluna de classificação é excluída após cada classificação.

0G`

A primeira entrada é, portanto, agora o resultado desejado.

Nota: A restrição na escolha do retângulo de uma determinada área foi flexibilizada e a seguinte versão de 144 143 bytes prefere um retângulo mais largo do que alto:

Lw$`(?<=(.*\n)*((.)*))(?=(.))((.)*(?<=(.*))\4)((.*\n)*((?>(?<-3>.)*)(?=\4)(?>(?<-6>.)*))\4)?
-$.($5$#9*$5);$.2,$#1,$.7,$.($#1*_$#9*
N`
0G`
.*;

Experimente online!

Gelatina , (27?)  29  28 bytes

^{27 se a indexação baseada em 1 for permitida - remova o final ’}

Fṙ1s2;Uœị³EaZI‘P
ZLpLŒċÇÞṪF’

Um programa completo.

Experimente online! (ou veja o outro caso de teste )

Quão?

Fṙ1s2;Uœị³EaZI‘P - Link 1, areaOrZero: list of pairs [[b,l],[t,r]]
F                - flatten the input                 [b,l,t,r]
 ṙ1              - rotate left one                   [l,t,r,b]
   s2            - split into twos                   [[l,t],[r,b]]
      U          - upend the input                   [[l,b],[r,t]]
     ;           - concatenate                       [[l,t],[r,b],[l,b],[r,t]]
         ³       - program's input
       œị        - multidimensional index into
          E      - all equal?                       X
            Z    - transpose the input              [[b,t],[l,r]]
           a     - logical AND (vectorises)         (if not X we now have [[0,0],[0,0]]
             I   - incremental differences          [t-b,r-l] (or [0,0] if not X)
              ‘  - increment (vectorises)           [t-b+1,r-l+1] (or [1,1] if not X)
               P - product                          area (or 1 if not X)

ZLpLŒċÇÞṪF’ - Main link: list of lists
Z           - transpose the input
 L          - length
   L        - length of the input
  p         - Cartesian product
    Œċ      - pairs with replacement
       Þ    - (stable) sort by:
      Ç     -   last link (1) as a monad
        Ṫ   - tail (note that the rightmost pre-sort represents the bottom-right 1x1
            -       so cannot be superseded by a non-matching rectangle)
         F  - flatten
          ’ - decrement (vectorises) (to get to 0-based indexing)

Perl 6 , 83 73 bytes

{([X] (^$^a[0]X ^$a)xx 2).max:{[eq] $a[.[*;1];.[*;0]]and[*] 1 X-[Z-] $_}}

Experimente online!

Retorna uma lista de listas ((x0 y0) (x1 y1)).

Explicação

{
  ([X]                   # Cross product of corner pairs.
    (^$^a[0]             # Range of x coords.
     X                   # Cross product of coords.
     ^$a                 # Range of y coords.
    )xx 2                # Duplicate list.
  ).max:                 # Find maximum of all ((x0 y0) (x1 y1)) lists
  {                      # using the following filter.
    [eq]                 # All letters equal?
      $a[.[*;1];.[*;0]]  # Multidimensional subscript with y and x coord pairs.
    and                  # Stop if false.
    [*]                  # Multiply
      1 X-[Z-] $_        # for each axis 1 - (c0 - c1) == c1 - c0 + 1.
  }
}

Haskell , 144 bytes

import Data.Array
o=assocs
f r=snd$maximum[((c-a+1)*(d-b+1),[a,b,c,d])|((a,b),x)<-o r,((c,d),y)<-o r,x==y,r!(a,d)==r!(c,b),x==r!(a,d),a<=c,b<=d]

Experimente online!

Gelatina , 24 bytes

XLṭLp`€p/⁺œị€EɗÐfI‘PɗÞ0Ṫ

Experimente online!

⁺ prova ser útil.

Formato de saída: [superior, inferior], [esquerda, direita] . Indexação 1.

JavaScript (ES6), 121 bytes

-1 byte graças a @ l4m2
-1 byte graças a @tsh
+2 bytes para cumprir com a nova regra de pontuação de retângulos

Recebe entrada como uma matriz de seqüências de caracteres. Retorna coordenadas indexadas em 0: [x0, y0, x1, y1] .

a=>a.map(b=(r,y)=>r.map((v,x)=>a.map((R,Y)=>R.map((V,X)=>V+R[x]+r[X]!=v+v+v|(A=(x+~X)*(y+~Y))<b||(o=[x,y,X,Y],b=A)))))&&o

Experimente online!

APL (Dyalog Classic) , 38 bytes

a⊃⍨⊃⍒×/1+-/↑2 2∘⍴¨a←⍸≢¨↑∘.(∩¨)⍨∘.∩¨⍨↓⎕

Experimente online!

Java 8, 208 205 bytes

m->{int r=0,R[]={},i=m.length,j,y,z,u,t,T;for(;i-->0;)for(j=m[i].length;j-->0;)for(y=i*j;y-->0;)if((T=m[i][j])==m[u=y/j][z=y%j]&T==m[i][z]&T==m[u][j]&r<(t=(i-u)*(j-z))){r=t;R=new int[]{z,u,j,i};}return R;}

Definitivamente, posso jogar golfe. Agora, uso a abordagem mais óbvia do uso de quatro três for-loops aninhados.

-3 bytes graças ao @ceilingcat combinando os loops internos de linhas e colunas em um único loop.

Explicação:

Experimente online.

m->{                         // Method with char-matrix parameter and int-array return-type
  int r=0,                   //  Largest area found, starting at 0
      R[]={},                //  Result coordinates, starting empty
      i=m.length,j,          //  x,y indices of the first corner
      y,z,                   //  x,y indices of the second corner
      u,t,T;                 //  Temp integers to reduce bytes
  for(;i-->0;)               //  Loop `i` over the rows
    for(j=m[i].length;j-->0;)//   Inner loop `j` over the columns
      for(y=i*j;y-->0;)      //    Inner loop over the rows and columns
        if((T=m[i][j])==m[u=y/j][z=y%j]
                             //      If the values at coordinates [i,j] and [y,z] are equal
           &T==m[i][z]       //      as well as the values at [i,j] and [i,z]
           &T==m[u][j]       //      as well as the values at [i,j] and [y,j]
           &r<(t=(i-u)*(j-z))){
                             //      And the current area is larger than the largest
          r=t;               //       Set `r` to this new largest area
          R=new int[]{z,u,j,i};}
                             //       And save the coordinates in `R`
  return R;}                 //  Return the largest rectangle coordinates `R`