首先，有几个辅助函数：
//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
然后，完成水平方向、行之后，我们现在对列执行完全相同的操作。这使用了transposeScala 标准集合库中提供的方法可根据同名的数学矩阵运算来交换行列。完成后我们也会转回。
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，并向右扫描，该行中有 2 个相邻单元格包含1。向下扫描，有两个相邻单元格具有包含该值的相同属性1并且在其右侧具有相同数量的相等值。
整理、转换形式的嵌套元组后会更清晰一些((a,b),c) to (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)
Where 1,(2,2)引用包含该值的单元格1，并且位于具有相似值的单元格的 2x2 矩形的左上角。
从这里开始，找到相同大小的矩形就很简单了。不过，如果您还想排除属于较大矩形子集的区域，则需要做更多的工作。
UPDATE:正如所写，该算法对于像 (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)) } }
}
UPDATE2
抓紧你的帽子，这是一个大帽子......
在编写一行新功能之前，我们首先进行一些重构，通过隐式转换将一些方法拉入 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)pairs 方法接受一个函数作为参数，为每个这样的对创建一个输出值。这个以后会派上用场的...
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 个参数块而不是 1 个？我很快就会解释。
I could已将这些定义为方法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) }
作为元组的替代方案，这确实有助于调试。深层嵌套的括号是not容易伤害眼睛。 （对不起 Lisp 粉丝！）
...并使用上面定义的函数：
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 and width）然后返回(cell,width) Tuple.
这也是我在定义函数时使用两个参数块的原因，因此第二个参数可以在 { 大括号 } 中传递，并使整个事情变得很好并且类似于 DSL。
Another 很重要这里说明的原理是类型推断器连续作用于参数块，因此对此（还记得吗？）：
def withRowRunLengths[T,U](grid: Grid[T])(func: (T,Int)=>U)
方式T将由提供的网格确定。然后，编译器知道作为第二个参数提供的函数的输入类型，-Int在这种情况下，因为第一个参数是Grid[Int]- 这就是为什么我能够写case (cell,width) => (cell,width)并且不必在任何地方明确说明cell and width是整数。在第二种用法中，Grid[(Int,Int)]已提供，适合封口case ((cell,width),height) => Rect(width,height)再说一遍，它确实有效。
如果该闭包包含任何不适用于网格底层类型的内容，那么编译器会抱怨，这就是类型安全的全部内容......
计算出所有可能的矩形后，剩下的就是收集数据并以更适合分析的格式呈现。因为这个阶段的嵌套可能会得到very混乱，我定义了另一种数据类型：
case class Cell[T](
value: T,
coords: (Int,Int) = (0,0),
widest: Rect = Rect.empty,
tallest: Rect = Rect.empty
)
这里没什么特别的，只是一个带有命名/默认参数的案例类。我也很高兴我有先见之明来定义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 结构，因为必要的坐标已嵌入到结果中。
Voila!
现在由您决定如何处理此列表。下一阶段可能是某种形式的排序和重复删除......
