c# - 如何在板(20x20)上进行图案/形状匹配/识别？

Question

棋盘是int[][]，我想找到这个形状

  1
    1
    1

使用棋盘上的所有 4 个对称(旋转)变体并记录位置。例如

      ...
      ...
  ... x x x x x x ...
  ... x x 1 1 x x ...
  ... x 1 x x x x ...
  ... x x x x x x ...
      ...
      ...

用F#来处理这类问题是不是更好一些？

下面是我的 c# 代码，仅用于垂直检查模式(水平检查代码类似)

    List<Position> GetMatchVertical(int reelID)
    {
        List<Position> ret = new List<Position>();

        var myReel = board[reelID];
        var leftReel = reelID - 1 >= 0 ? board[reelID - 1] : null;
        var rightReel = reelID + 1 < boardSize ? board[reelID + 1] : null;

        int currentColor = myReel[0];

        for (int reelPosition = 1; reelPosition < boardSize; reelPosition++)
        {
            int nextColor = myReel[reelPosition];
            if (currentColor == nextColor)
            {
                if (leftReel!=null)
                {
                    if (reelPosition + 1 < boardSize && leftReel[reelPosition + 1] == currentColor)
                    {
                        ret.Add(logPosition(...));
                    }
                }
                if (rightReel!=null)
                {
                    if (reelPosition - 2 >= 0 && rightReel[reelPosition - 2] == currentColor)
                    {
                        ret.Add(logPosition(...));
                    }
                }
            }
            else
            {
                currentColor = nextColor;
            }
        }

        return ret;
    }

Answer 1

这绝对非常适合函数式编程和 F#。有大量可能的方法。我认为 pad 的解决方案可能是最直接的解决方案，它是一个非常好的起点。如果您需要更通用的东西，那么 Huusom 的解决方案非常好。

还有更通用的方法，即构建领域特定语言 (DSL) 来检测数组中的模式。这是更高级的功能技术，但它非常适合您的示例。如果你这样做了，那么你就可以用一种非常简洁的方式来表达相当复杂的模式。这是一个例子:

// Create a detector that tests if a location
// contains 1 and returns 'false' when out of range
let one = border false (equals 1)

// A shape detector for your pattern
let pattern = 
  around (0, 0) one <&> around (1, 0) one <&> 
  around (-1, 1) one

// Test pattern with any rotation: Combine 
// 4 possible rotations with logical or.
let any = 
  pattern <|> rotate pattern <|> 
  rotate (rotate pattern) <|> 
  rotate (rotate (rotate pattern))

此示例使用各种原语来构建模式的声明性规范。值 any 表示一个函数，您可以运行该函数来测试模式是否出现在给定位置。它处理模式的所有旋转，还进行边界检查。您还需要添加镜像模式，但这很容易扩展。

解释实现可能需要一篇完整的博文，但这里有一段注释过的源代码，应该非常易读:

/// A type that represents a function that tests
/// whether an array contains some pattern at a 
/// specified location. It gets the location to 
/// test & the array as arguments and returns bool.
type ShapeDetector = SD of (int -> int -> int[,] -> bool)

/// A primitive that tests whether the value at the
/// current location contains a value 'v'
let equals v = SD (fun x y arr -> arr.[x,y] = v)

/// A combinator that takes 'ShapeDetector' and 
/// creates a new one that returns 'def' when 
/// accessing outside of the array bounds
let border def (SD f) = SD (fun x y arr -> 
  if x < 0 || y < 0 || x >= arr.GetLength(0) || y >= arr.GetLength(1) 
  then def else f x y arr)

/// A combinator that calls a given ShapeDetector
/// at a location specified by offset dx, dy
let around (dx, dy) (SD f) = SD (fun x y arr ->
  f (x + dx) (y + dy) arr)

/// A combinator that takes a ShapeDetector and
/// builds a new one, which is rotated by 90 degrees
let rotate (SD f) = SD (fun x y arr ->
  f -y x arr)

/// Creates a shape detector that succeeds only
/// when both of the arguments succeed.
let (<&>) (SD f1) (SD f2) = SD (fun x y arr ->
  f1 x y arr && f2 x y arr)

/// Creates a shape detector that succeeds 
/// when either of the arguments succeed.
let (<|>) (SD f1) (SD f2) = SD (fun x y arr ->
  f1 x y arr || f2 x y arr)

最后，这是一个在样本二维阵列上运行模式检测器的示例:

// Create a 2D array as a sample input
let inp = 
  array2D [ [ 0; 0; 1 ]
            [ 0; 1; 0 ]
            [ 0; 1; 0 ] ]

// Get the underlying function and run it
// for all possible indices in the array
let (SD f) = any
for x in 0 .. 2 do
  for y in 0 .. 2 do
    printfn "%A %A" (x, y) (f x y inp)