Вы можете сделать это в O(n^2) относительно легко.
Во-первых, некоторые предварительные расчеты. Для каждой ячейки в матрице подсчитайте, сколько последовательных ячеек под ней имеют одинаковый номер.
В вашем примере результирующая матрица a (не могу придумать лучшего имени:/) будет выглядеть так

0 0 0 0 0 2 2
1 1 2 2 2 1 1
0 0 1 1 1 0 0
1 1 0 0 0 1 1
0 0 0 0 0 0 0

Его можно легко изготовить в O(n^2).

Теперь для каждой строки i найдем все прямоугольники с верхней стороной в строке i (и нижней стороной в строке i + height - 1).
Вот иллюстрация для i = 1

0 0 0 0 0 0 0
-------------
4 4 2 2 2 0 0
4 4 2 2 2 0 0
0 0 2 2 2 1 1
-------------
0 0 0 0 0 1 1

Теперь основная мысль

int current_width = 0;
for (int j = 0; j < matrix.width; ++j) {
    if (a[i][j] < height - 1) {
        // this column has different numbers in it, no game
        current_width = 0;
        continue;
    }

    if (current_width > 0) {
        // this column should consist of the same numbers as the one before
        if (matrix[i][j] != matrix[i][j - 1]) {
            current_width = 1; // start streak anew, from the current column
            continue;
        }
    }

    ++current_width;
    if (current_width >= width) {
        // we've found a rectangle!
    }
}

В приведенном выше примере (i = 1) current_width после каждой итерации будет 0, 0, 1, 2, 3, 0, 0.

Теперь нам нужно перебрать все возможные i, и у нас есть решение.

Во-первых, пара вспомогательных функций:

//count the number of elements matching the head
def runLength[T](xs:List[T]) = xs.takeWhile(_ == xs.head).size

//pair each element with the number of subsequent occurrences
def runLengths[T](row:List[T]) : List[(T,Int)] = row match {
  case Nil => Nil
  case h :: t => (h, runLength(row)) :: runLengths(t)
}
//should be optimised for tail-call, but easier to understand this way

//sample input: 1,1,2,2,2,3,4,4,4,4,5,5,6
//output: (1,2), (1,1), (2,3), (2,2), (2,1), (3,1), (4,4), (4,3), (4,2), (4,1), (5,2), (5,1), (6,1)

Затем это можно использовать для каждой строки в сетке:

val grid = List(
  List(0,0,0,0),
  List(0,1,1,0),
  List(0,1,1,0),
  List(0,0,0,0))

val stage1 = grid map runLengths
// returns stage1: List[List[(Int, Int)]] =
// 0,4  0,3  0,2  0,1
// 0,1  1,2  1,1  0,1
// 0,1  1,2  1,1  0,1
// 0,4  0,3  0,2  0,1

Затем проделав горизонтали, ряды, теперь точно такую ​​же операцию проделываем со столбцами. При этом используется метод transpose, доступный в стандартной библиотеке коллекций Scala, для обмена строк‹->столбцы в соответствии с одноименной операцией математической матрицы. Мы также транспонируем обратно, как только это будет сделано.

val stage2 = (stage1.transpose map runLengths).transpose
// returns stage2: List[List[((Int, Int), Int)]] =
// (0,4),1  (0,3),1  (0,2),1  (0,1),4
// (0,1),2  (1,2),2  (1,1),2  (0,1),3
// (0,1),1  (1,2),1  (1,1),1  (0,1),2
// (0,4),1  (0,3),1  (0,2),1  (0,1),1

Что это значит? Взяв один элемент: (1,2),2, это означает, что эта ячейка содержит значение 1, и просканировав вправо, вы увидите, что в строке, содержащей 1, есть 2 соседние ячейки. Просматривая вниз, есть две соседние ячейки с одинаковым свойством содержания значения 1 и с одинаковым количеством одинаковых значений справа от них.

Немного понятнее после приведения в порядок, преобразования вложенных кортежей вида ((a,b),c) в (a,(b,c)):

val stage3 = stage2 map { _.map {case ((a,b),c) => a->(b,c) } }
//returns stage3: List[List[(Int, (Int, Int))]] =
//  0,(4,1)  0,(3,1)  0,(2,1)  0,(1,4)
//  0,(1,2)  1,(2,2)  1,(1,2)  0,(1,3)
//  0,(1,1)  1,(2,1)  1,(1,1)  0,(1,2)
//  0,(4,1)  0,(3,1)  0,(2,1)  0,(1,1)

Где 1,(2,2) относится к ячейке, содержащей значение 1 и находящейся в верхнем левом углу прямоугольника 2x2 ячеек с одинаковыми значениями.

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

ОБНОВЛЕНИЕ: как написано, алгоритм плохо работает для таких случаев, как ячейка в (0,0), которая принадлежит двум различным прямоугольникам (1x4 и 4x1). При необходимости это также можно решить с помощью тех же методов. (выполните один проход с помощью map/transpose/map/transpose и второй с помощью transpose/map/transpose/map, затем заархивируйте и сведите результаты).

Его также потребуется изменить, если ввод может содержать соседние прямоугольники, содержащие ячейки с одинаковым значением, например:

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

Собираем все вместе и немного чистим:

type Grid[T] = List[List[T]]

def runLengths[T](row:List[T]) : List[(T,Int)] = row match {
  case Nil => Nil
  case h :: t => (h -> row.takeWhile(_ == h).size) :: runLengths(t)
}

def findRectangles[T](grid: Grid[T]) = {
  val step1 = (grid map runLengths)
  val step2 = (step1.transpose map runLengths).transpose
  step2 map { _ map { case ((a,b),c) => (a,(b,c)) } }
}

ОБНОВЛЕНИЕ2

Придержите свои шляпы, это большое дело...

Прежде чем написать одну строку новой функциональности, мы сначала немного рефакторим, перетащив некоторые методы в классы Ops с неявными преобразованиями, чтобы их можно было использовать, как если бы они были методами, определенными для базовых типов коллекций:

import annotation.tailrec

class RowOps[T](row: List[T]) {
  def withRunLengths[U](func: (T,Int)=>U) : List[U] = {
    @tailrec def recurse(row:List[T], acc:List[U]): List[U] = row match {
      case Nil => acc
      case head :: tail =>
        recurse(
          tail,
          func(head, row.takeWhile(head==).size) :: acc)
    }
    recurse(row, Nil).reverse
  }

  def mapRange(start: Int, len: Int)(func: T=>T) =
    row.splitAt(start) match {
      case (l,r) => l ::: r.take(len).map(func) ::: r.drop(len)
    }
}

implicit def rowToOps[T](row: List[T]) = new RowOps(row)

Это добавляет метод withRunLengths в списки. Одно заметное отличие заключается в том, что вместо возврата списка (value, length) пар метод принимает в качестве параметра функцию для создания выходного значения для каждой такой пары. Это пригодится позже...

type Grid[T] = List[List[T]]

class GridOps[T](grid: Grid[T]) {
  def deepZip[U](other: Grid[U]) = (grid zip other) map { case (g,o) => g zip o}
  def deepMap[U](f: (T)=>U) = grid map { _ map f}
  def mapCols[U](f: List[T]=>List[U]) = (grid.transpose map f).transpose
  def height = grid.size
  def width = grid.head.size
  def coords = List.tabulate(height,width){ case (y,x) => (x,y) }
  def zipWithCoords = deepZip(coords)
  def deepMapRange(x: Int, y: Int, w: Int, h: Int)(func: T=>T) =
    grid mapRange (y,h){ _.mapRange(x,w)(func) }
}

implicit def gridToOps[T](grid: Grid[T]) = new GridOps(grid)

Здесь не должно быть сюрпризов. Методы deepXXX избегают необходимости писать конструкции вида list map { _ map { ... } }. tabulate также может быть для вас новым, но, надеюсь, его назначение очевидно из использования.

Используя их, становится тривиальным определение функций для нахождения горизонтальной и вертикальной длины пробега по всей сетке:

def withRowRunLengths[T,U](grid: Grid[T])(func: (T,Int)=>U) =
  grid map { _.withRunLengths(func) }

def withColRunLengths[T,U](grid: Grid[T])(func: (T,Int)=>U) =
  grid mapCols { _.withRunLengths(func) }

Почему 2 блока параметров, а не один? Я объясню в ближайшее время.

Я мог бы определить их как методы в GridOps, но они не кажутся подходящими для общего использования. Здесь можно со мной не согласиться :)

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

def parseIntGrid(rows: String*): Grid[Int] =
  rows.toList map { _ map {_.toString.toInt} toList }

val input: Grid[Int] = parseIntGrid("0000","0110","0110","0000")

...еще один полезный вспомогательный тип...

case class Rect(w: Int, h: Int)
object Rect { def empty = Rect(0,0) }

в качестве альтернативы кортежу это действительно помогает при отладке. Глубоко вложенные скобки не очень бросаются в глаза. (извините, фанаты Лиспа!)

... и используйте функции, определенные выше:

val stage1w = withRowRunLengths(input) {
  case (cell,width) => (cell,width)
}

val stage2w = withColRunLengths(stage1w) {
  case ((cell,width),height) => Rect(width,height)
}


val stage1t = withColRunLengths(input) {
 case (cell,height) => (cell,height)
}

val stage2t = withRowRunLengths(stage1t) {
  case ((cell,height),width) => Rect(width,height)
}

Все вышеперечисленные блоки должны быть однострочными, но я переформатировал для StackOverflow.

Выходные данные на этом этапе — это просто сетки прямоугольников, я намеренно опустил любое упоминание фактического значения, из которого состоит прямоугольник. Это абсолютно нормально, его достаточно легко найти по его координатам в сетке, и мы через короткое время рекомбинируем данные.

Помните, я объяснял, что RowOps#withRunLengths принимает функцию в качестве параметра? Ну, вот где это используется. case (cell,width) => (cell,width) на самом деле является функцией, которая принимает значение ячейки и длину цикла (называя их cell и width), а затем возвращает кортеж (cell,width).

По этой же причине я использовал два блока параметров при определении функций, так что второй параметр можно передать в { фигурных скобках }, что делает все это красивым и похожим на DSL.

Еще один очень важный принцип, проиллюстрированный здесь, заключается в том, что механизм вывода типов работает с блоками параметров последовательно, поэтому для этого (помните?):

def withRowRunLengths[T,U](grid: Grid[T])(func: (T,Int)=>U)

Тип T будет определяться предоставленной сеткой. Затем компилятор знает тип ввода для функции, предоставленной в качестве второго аргумента, - в данном случае Int, поскольку первым параметром было Grid[Int] - поэтому я смог написать case (cell,width) => (cell,width) и не имел чтобы явно указать, что cell и width являются целыми числами. При втором использовании предоставляется Grid[(Int,Int)], это соответствует закрытию case ((cell,width),height) => Rect(width,height), и опять же, это просто работает.

Если бы это закрытие содержало что-то, что не работало бы для базового типа сетки, тогда компилятор пожаловался бы, это то, что касается безопасности типов...

Рассчитав все возможные прямоугольники, остается собрать данные и представить их в более удобном для анализа формате. Поскольку вложение на этом этапе могло стать очень беспорядочным, я определил другой тип данных:

case class Cell[T](
  value: T,
  coords: (Int,Int) = (0,0),
  widest: Rect = Rect.empty,
  tallest: Rect = Rect.empty
)

Здесь ничего особенного, просто класс case с именованными параметрами/параметрами по умолчанию. Я также рад, что предусмотрительно определил Rect.empty выше :)

Теперь смешайте 4 набора данных (входные значения, координаты, самые широкие прямоугольники, самые высокие прямоугольники), постепенно разложите по ячейкам, аккуратно перемешайте и подавайте:

val cellsWithCoords = input.zipWithCoords deepMap {
  case (v,(x,y)) => Cell(value=v, coords=(x,y))
}

val cellsWithWidest = cellsWithCoords deepZip stage2w deepMap {
  case (cell,rect) => cell.copy(widest=rect)
}

val cellsWithWidestAndTallest = cellsWithWidest deepZip stage2t deepMap {
  case (cell,rect) => cell.copy(tallest=rect)
}

val results = (cellsWithWidestAndTallest deepMap {
  case Cell(value, coords, widest, tallest) =>
    List((widest, value, coords), (tallest, value, coords))
  }
).flatten.flatten

Последний этап здесь интересен, он преобразует каждую ячейку в список кортежей размером 2 (прямоугольник, значение, координаты) (размер 2, потому что у нас есть и самые широкие, и самые высокие прямоугольники для каждой ячейки). Двойной вызов flatten затем возвращает полученное List[List[List[_]]] обратно к одному List. Больше нет необходимости сохранять 2D-структуру, так как необходимые координаты уже встроены в результаты.

Вуаля!

Теперь вам решать, что вы будете делать с этим списком. Следующим этапом, вероятно, является какая-то форма сортировки и удаления дубликатов...

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

Во-первых, вычисление последовательных ячеек с одинаковым номером под ячейкой. Я сделал небольшое изменение, вернув все значения плюс один по сравнению с предложенным Никитой выводом, чтобы избежать - 1 в какой-то другой части кода.

def computeHeights(column: Array[Int]) = (
    column
    .reverse
    .sliding(2)
    .map(pair => pair(0) == pair(1))
    .foldLeft(List(1)) ( 
        (list, flag) => (if (flag) list.head + 1 else 1) :: list
    )
)

Я бы предпочел использовать .view перед реверсированием, но это не работает с текущей версией Scala. Если бы это было так, это позволило бы избежать повторных создания массивов, что должно значительно ускорить код, если не из соображений локальности памяти и пропускной способности.

Теперь все столбцы одновременно:

import scala.actors.Futures.future

def getGridHeights(grid: Array[Array[Int]]) = (
    grid
    .transpose
    .map(column => future(computeHeights(column)))
    .map(_())
    .toList
    .transpose
)

Я не уверен, окупятся ли здесь накладные расходы на распараллеливание или нет, но это первый алгоритм в Stack Overflow, где у него действительно есть шанс, учитывая нетривиальные усилия по вычислению столбца. Вот еще один способ написать это, используя будущие функции 2.9 (это может работать на Scala 2.8.1 - не уверен, что:

def getGridHeights(grid: Array[Array[Int]]) = (
    grid
    .transpose
    .toParSeq
    .map(computeHeights)
    .toList
    .transpose
)

Теперь суть алгоритма Никиты:

def computeWidths(height: Int, row: Array[Int], heightRow: List[Int]) = (
    row
    .sliding(2)
    .zip(heightRow.iterator)
    .toSeq
    .reverse
    .foldLeft(List(1)) { case (widths @ (currWidth :: _), (Array(prev, curr), currHeight)) =>
        (
            if (currHeight >= height && currWidth > 0 && prev == curr) currWidth + 1
            else 1
        ) :: widths
    }
    .toArray
)

Я использую сопоставление с образцом в этом фрагменте кода, хотя меня беспокоит его скорость, потому что со всеми скольжением, сжатием и складыванием здесь жонглируют двумя многими вещами. И, говоря о производительности, я использую Array вместо IndexedSeq, потому что Array — единственный тип в JVM, который не стирается, что приводит к гораздо лучшей производительности с Int. И, кроме того, есть .toSeq, которым я тоже не очень доволен из-за локальности памяти и пропускной способности.

Кроме того, я делаю это справа налево, а не слева направо, как у Никиты, просто чтобы найти верхний левый угол.

Однако это то же самое, что и код в ответе Никиты, за исключением того факта, что я все еще добавляю единицу к текущей ширине по сравнению с его кодом и не печатаю результат прямо здесь. Однако здесь есть куча вещей без ясного происхождения — row, heightRow, height... Давайте посмотрим на этот код в контексте — и распараллелив! - чтобы получить общую картину.

def getGridWidths(height: Int, grid: Array[Array[Int]]) = (
    grid
    .zip(getGridHeights(grid))
    .map { case (row, heightsRow) => future(computeWidths(height, row, heightsRow)) }
    .map(_())
)

И версия 2.9:

def getGridWidths(height: Int, grid: Array[Array[Int]]) = (
    grid
    .toParSeq
    .zip(getGridHeights(grid))
    .map { case (row, heightsRow) => computeWidths(height, row, heightsRow) }
)

И, для финала,

def findRectangles(height: Int, width: Int, grid: Array[Array[Int]]) = {
    val gridWidths = getGridWidths(height, grid)
    for {
        y <- gridWidths.indices
        x <- gridWidths(y).indices
        if gridWidths(y)(x) >= width
    } yield (x, y)
}

Так что... Я не сомневаюсь, что императивная версия алгоритма Никиты быстрее -- она ​​использует только Array, который намного быстрее с примитивами, чем любой другой тип, и позволяет избежать массового создания временных коллекций -- хотя Scala мог сделать лучше здесь. Кроме того, никаких замыканий — они хоть и помогают, но работают медленнее, чем код без замыканий. По крайней мере, пока JVM не вырастет что-нибудь, чтобы помочь с ними.

Кроме того, код Никиты можно легко распараллелить с помощью потоков — самое главное! -- с небольшими трудностями.

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

ИЗМЕНИТЬ

Итак, я решил попробовать сделать эффективную функциональную версию. На самом деле он не полностью функционален, потому что я использую Iterator, который можно изменить, но он достаточно близок. К сожалению, он не будет работать на Scala 2.8.1, потому что ему не хватает scanLeft на Iterator.

Здесь есть еще две неприятные вещи. Во-первых, я отказался от распараллеливания высот сетки, так как не мог обойтись хотя бы одним transpose со всеми вытекающими отсюда копиями коллекций. Тем не менее, есть по крайней мере одно копирование данных (см. вызов toArray, чтобы понять, где именно).

Кроме того, поскольку я работаю с Iterable, я теряю возможность использовать параллельные коллекции. Интересно, нельзя ли было бы улучшить код, если бы grid с самого начала было параллельной коллекцией параллельных коллекций.

Я понятия не имею, является ли это более эффективным, чем предыдущая версия или нет. Это интересный вопрос...

def getGridHeights(grid: Array[Array[Int]]) = (
    grid
    .sliding(2)
    .scanLeft(Array.fill(grid.head.size)(1)) { case (currHeightArray, Array(prevRow, nextRow)) =>
        (prevRow, nextRow, currHeightArray)
        .zipped
        .map { case (x, y, currHeight) =>  if (x == y) currHeight + 1 else 1 }
    }
)

def computeWidths(height: Int, row: Array[Int], heightRow: Array[Int]) = (
    row
    .sliding(2)
    .map { case Array(x, y) => x == y }
    .zip(heightRow.iterator)
    .scanLeft(1) { case (currWidth , (isConsecutive, currHeight)) =>
        if (currHeight >= height && currWidth > 0 && isConsecutive) currWidth + 1
        else 1
    }
    .toArray
)

import scala.actors.Futures.future

def getGridWidths(height: Int, grid: Array[Array[Int]]) = (
    grid
    .iterator
    .zip(getGridHeights(grid))
    .map { case (row, heightsRow) => future(computeWidths(height, row, heightsRow)) }
    .map(_())
    .toArray
)

def findRectangles(height: Int, width: Int, grid: Array[Array[Int]]) = {
    val gridWidths = getGridWidths(height, grid)
    for {
        y <- gridWidths.indices
        x <- gridWidths(y).indices
        if gridWidths(y)(x) >= width
    } yield (x - width + 1, y - height + 1)
}