Самый большой прямоугольник в 2d массиве

26

вход

Доска: 2D контейнер (матрица, список списков и т. Д.) Букв, таких как:

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

Если вы выбираете список списков, вы можете предположить, что все списки имеют одинаковую длину.

правила

  • Чтобы сделать правильный прямоугольник, вам нужны все углы прямоугольника с одинаковыми буквами.
  • Пример, посмотрите образец платы с X ниже. Вы можете увидеть 'X' на (1,0) также на (4,0) также на (1,3) и на (4,3), тогда у вас есть прямоугольник [1,0,4,3], что означает из (1,0) - (4,3):

Образец платы с 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"]
  • Цель состоит в том, чтобы найти прямоугольник или один из прямоугольников с наибольшей площадью, рассчитанной по формуле (правый левый + 1) * (нижний верх + 1)
  • Если имеется несколько прямоугольников с одинаковой максимальной площадью, выведите любой. Опционально тот, который (верхняя координата, левая координата, правая координата, нижняя координата) лексикографически наименьший.
  • Прямоугольники должны иметь края, параллельные краю доски.
  • Каждая буква представляет собой печатный символ ASCII от A до Z (оба включены).

Выход

Выходными данными должны быть положения слева и справа от углов прямоугольника наибольшей площади. Для первого примера «доски» большой квадрат - желтый:

введите описание изображения здесь

И ответ должен быть:

[1, 1, 8, 4]

Второй пример теста

Ввод:

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

Должен дать один из этих трех списков координат, идентифицирующих область из шести прямоугольников:

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

Этот вопрос размещен в переполнении стека с заголовком: Как найти самый большой прямоугольник в двумерном массиве, образованном четырьмя одинаковыми углами? и с этим грубым решением JS (я могу сказать "грубо", потому что это мой код;):

Хорошо, это мой первый пост, будь терпим со мной, пожалуйста. Я изменю все, что вы говорите, чтобы улучшить тест.

danihp
источник
7
Привет, добро пожаловать в PPCG! Это кажется хорошим испытанием, но, похоже, не хватает критерия выигрыша. Как правило, сообщения здесь помечены [code-golf], что означает, что выигрывает самый короткий код (в байтах).
Конор О'Брайен
1
Я подумал, что дам вам знать, что у нас есть песочница, которую вы можете использовать для получения отзывов по вопросам до того, как они будут опубликованы на основном сайте. Песочница полезна почти всем здесь, но особенно новичкам, которые могут не знать всех наших правил и ожиданий.
Wheat Wizard
2
В некоторых ответах координаты выводятся в порядке сортировки для «первого» прямоугольника (т. Е. Сверху, слева, снизу, справа) вместо (слева, сверху, справа, снизу), как показано в ваших примерах. Это нормально?
Ними,
2
Менее строгие форматы вывода обычно поощряют больше ответов, поэтому что-то вроде ((left,top),(right,bottom))этого тоже должно быть хорошо. Я удалил свой ответ и снова отвечу, когда вопрос будет полностью уточнен.
Анг
1
Конечно, если вы собираетесь принять ответ, он должен быть самым коротким, именно так большинству людей нравится то, что делается на сайте. Однако нет никаких последствий для этого. Существует также растущее мнение, что принятие ответов наносит ущерб сайту. Я придерживаюсь этого мнения и поэтому никогда не принимаю ответы на свои вопросы. То, что вы делаете, зависит от вас.
Пшеничный волшебник

Ответы:

6

Python 2 , 148 130 байт

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:]

Попробуйте онлайн!

овс
источник
Привет @ovs, тебе неудобно, если я поменяю правило для определения площади на: (x2-x1 + 1) × (y2-y1 + 1), как предположил Анг?
danihp
Я хотел бы ослабить некоторые правила, чтобы поощрить больше ответов. Могу я?
Данихп
@danihp Продолжай. Это не лишает законной силы мой ответ, верно?
овс
Нет, ваш ответ правильный! Ницца.
Данихп
5

Сетчатка , 163 162 байта

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

0G`

Попробуйте онлайн! Редактировать: 1 байт сохранен, потому что конечное )соответствие $.(неявно. Объяснение:

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

Это регулярное выражение соответствует прямоугольникам. Группы следующие: 1) Верхний ряд (по количеству захвата) 2) Левый столбец (как длина) 3) Балансировка для выравнивания левых углов 4) Буква для углов 5) Ширина + 1 (как длина) 6) Балансировка чтобы обеспечить выравнивание правых углов 7) Правый столбец (как длина) 8) Неиспользуемый 9) Высота (как счетчик захвата). В wопции гарантирует , что все возможные ширины прямоугольников совпадающие для каждого заданных в левом верхнем углу. В $опции приведены результаты , используя следующую схему замещения.

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

Подстановки следующие: правый столбец, верхний ряд, левый столбец, отрицание площади прямоугольника (буквально рассчитывается как длина повторения строки ширины на единицу больше высоты число раз), левый столбец верхний ряд, правый столбец, за которым следует выражение, которое оценивает нижний ряд (перехват стоил бы 12 байт плюс у меня кончились однозначные переменные). Первые четыре захвата представляют порядок сортировки в порядке приоритета. Поскольку Retina сортирует стабильно, сортировка по нескольким столбцам может быть установлена ​​путем сортировки по каждому столбцу сортировки по очереди от наименьшего к наибольшему приоритету. (Область должна быть отсортирована в порядке убывания, поэтому нельзя использовать сортировку по одной строке.)

4{N`

Затем выполняется четыре числовых вида.

)m`^.*?,

Столбец сортировки затем удаляется после каждой сортировки.

0G`

Поэтому первая запись теперь является желаемым результатом.

Примечание. С тех пор ограничение на выбор прямоугольника для данной области было ослаблено, и следующая 144 -байтовая версия 144 предпочитает более широкий, а не более высокий прямоугольник:

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

Попробуйте онлайн!

Нил
источник
Сбойное требование лексикографической-мин (попробовать тестовый случай я добавил к ОП, например) (может быть также выход может быть в неправильном порядке ??) TIO
Джонатан Allan
(... да, первые два значения в выходных данных неправильные, я думаю)
Джонатан Аллан
Я просто ослабил некоторые ограничения (лексикографическое минимальное требование). Я надеюсь, не будет проблемой для вас.
danihp
... теперь это должно соответствовать линиям и точкам.
Джонатан Аллан
Исправление лексикографического порядка стоило 20 байтов :-( и я заметил, что изменился расчет площади, что стоило еще 2 байта, но я не знаю, что @JonathanAllan означает о точках.
Нил,
4

Желе , (27?)  29  28 байт

27, если разрешена индексация на основе 1 - удалить трейлинг

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

Полная программа.

Попробуйте онлайн! (или посмотрите другой контрольный пример )

Как?

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)
Джонатан Аллан
источник
4

Perl 6 , 83 73 байта

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

Попробуйте онлайн!

Возвращает список списков ((x0 y0) (x1 y1)).

объяснение

{
  ([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.
  }
}
nwellnhof
источник
3

Haskell , 144 байта

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]

Попробуйте онлайн!

Angs
источник
Вы можете удалить b<=d, пока вы держите a<=c.
Wheat Wizard
@ovs на самом деле это тоже не сработает (см. пример, который я добавил TIO )
Джонатан Аллан
@nimi: Я могу поспорить, что это просто вопрос переноса ввода.
Анг
Это хорошо для меня. Вы можете транспонировать вход.
Данихп
3

JavaScript (ES6), 121 байт

-1 байт благодаря @ l4m2
-1 байт благодаря @tsh
+2 байта за соблюдение нового правила оценки прямоугольников

Принимает ввод в виде матрицы строк. Возвращает 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

Попробуйте онлайн!

Arnauld
источник
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
14 м2, 17
Если имеется несколько прямоугольников с одинаковой максимальной площадью, выведите любой ; может быть (A=...)<=b-> (A=...)<b?
TSH
@tsh Теперь это действительно безопасно. Благодарность!
Арно
1

Java 8, 208 205 байт

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;}

Определенно можно играть в гольф ... Сейчас я использую наиболее очевидный подход, используя четыре три вложенных цикла .

-3 байта благодаря @ceilingcat, объединяющему внутренние циклы строк и столбцов в один цикл.

Объяснение:

Попробуйте онлайн.

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`
Кевин Круйссен
источник