比赛地单曲得分最高

Question

背景

Match Land是一款移动游戏，它属于Match-3类型(想想珠宝系列或糖果粉碎系列)：交换两个正交相邻的棋子，使3排或更长。然而，Match Land有一个额外的规则，使游戏更加有趣。

一旦进行有效的匹配-3移动，匹配的块不会立即被移除；相反，您将得到一个小的时间窗口，您可以通过交换尚未匹配的块来创建更多/更长的匹配-3链。如果您做了一个错误的交换(这不会创建一个新的匹配或扩展现有的匹配)，您的回合将立即结束。

这个挑战的确切规则如下(我现在不玩这个游戏，所以细节可能与实际游戏不同。略去与这项挑战无关的细节)：

• 游戏是在长方形棋盘上进行的。它是基于回合的，玩家可以在一个回合中做一个或多个动作.
• 板上充满了瓷砖，每种瓷砖都有六种不同的类型之一(在后面的示例中表示为1到6)。
• 玩家通过交换两个正交(水平或垂直)相邻的瓷砖来进行“匹配”(一排中有三个或更多相同的瓷砖，水平或垂直)。交换两个瓷砖的动作称为“移动”。
• 初始比赛结束后，如果移动延长了现有匹配的长度，或者创建了至少一个新的匹配(3行)，则玩家可以进行额外的移动。在下面的示例中，B4-C4和B3-B4是有效的移动，但A3-B3不是有效的(只需在不创建一行3行的情况下移动现有匹配的4次就无效)：\x{e76f}1 2 3 4-+
• 玩家不能移动已经匹配的瓷砖。

例如，考虑以下5x7板(具有坐标以便于解释)：

  | 1  2  3  4  5  6  7
--+---------------------
A | 2  4  4  3  5  2  4
B | 3  2  1  4  1  3  5
C | 4  2  4  4  3  1  4
D | 2  4  3  1  4  2  3
E | 2  4  2  2  3  3  4

这名球员可以在A3-A4比赛中与3名4英尺的S比赛：

  | 1  2  3  4  5  6  7
--+---------------------
A | 2  4  3 (4) 5  2  4
B | 3  2  1 (4) 1  3  5
C | 4  2  4 (4) 3  1  4
D | 2  4  3  1  4  2  3
E | 2  4  2  2  3  3  4

然后D7-E7去匹配大约3's：

  | 1  2  3  4  5  6  7
--+---------------------
A | 2  4  3 (4) 5  2  4
B | 3  2  1 (4) 1  3  5
C | 4  2  4 (4) 3  1  4
D | 2  4  3  1  4  2  4
E | 2  4  2  2 (3)(3)(3)

然后是C5-D5 (请注意，只有当要匹配的新块与现有匹配对齐时，才会扩展匹配，因此移动到D5中的3与现有的E5-E7不匹配)：

  | 1  2  3  4  5  6  7
--+---------------------
A | 2  4  3 (4) 5  2  4
B | 3  2  1 (4) 1  3  5
C | 4  2 (4)(4)(4) 1  4
D | 2  4  3  1  3  2  4
E | 2  4  2  2 (3)(3)(3)

您可以继续这样做，直到您用尽可能的移动。

我从与26块相匹配的初始状态中发现了9个移动序列(如果是最优的话，还没有确认)：

C1-C2 B1-B2 A2-B2 C5-D5 D6-E6 E5-E6 D3-D4 B6-C6 B3-B4

  | 1  2  3  4  5  6  7
--+---------------------
A |(2) 3 (4) 3  5  2  4
B |(2)(4)(4)(1)(1)(1) 5
C |(2)(4)(4)(4)(4)(3) 4
D |(2)(4) 1 (3)(3)(3)(3)
E |(2)(4)(2)(2)(2)(3) 4

挑战

给定Match Land中的板状态，输出可以在一个回合中匹配的最大块数。

输入是一个从1到6包含的整数的2D数组。您可以在您的语言中使用矩形2D数组的任何等效表示形式，以及任何6个不同的值来代替整数。您还可以进一步假设输入没有任何三位一体(就像实际游戏中的情况一样)，并且至少有一个有效的初始移动。

适用标准的密码-高尔夫规则。以字节为单位的最短代码获胜。想象中的布朗尼点的解决方案，证明是正确的，并在实践中工作得相当快。

测试用例

Input:
1 1 2 1 1
Output: 4

Input:
1 1 2
2 2 3
3 3 1
Output: 9

Input:
2 2 1 2 1
2 1 2 1 2
3 2 1 2 1
Output: 14 (A3-A4, B4-B5, B2-B3, B3-B4, C3-C4)

Input:
3 2 1 2 2
2 1 2 1 2
3 2 1 2 1
Output: 12 (B4-C4, B2-C2, A2-A3)
(I believe matching 13 tiles is impossible without breaking existing matches)

Answer 1

R，239个字节

f=function(m,x=!m,w=nrow(m),`+`=sum,`/`=c){for(i in seq(m))for(j in 0:1){l=m
k=i--(i%%w&!j)-j*w*(i>w)
l[i/k]=l[k/i]
n=0
for(d in 1:2)n=t(n|apply(l,d,function(v,r=rle(v)$l)unlist(Map(rep,r>2,r)))&!+x[i/k])
if(+n>+x)F=max(F,+n,f(l,t(n)))}
F}

在网上试试！

半裸

# m - input matrix
# x - matrix of existing matches initialized with FALSEs of the shape of m
# w - number of rows
f = function(m, x=!m, w=nrow(m)) {
  # loop through each cell in m twice: 
  # once for a vertical match and once for a horizontal one
  for(i in seq(m)) for(j in 0:1) {
    # Work on a copy of m
    l = m
    # The index of the cell to swap:
    # one cell down from i (except the last row), or
    # one cell left from i (except the first column)
    k = i + (i%%w&!j) - j*w*(i>w) 
    # Swap ith and kth cell
    l[c(i,k)] = l[c(k,i)]
    # Record new matches, start with 0
    n = 0
    # If neither i, nor k was matched earlier, check both dimensions:
    if(!any(x[c(i,k)])) for(d in 1:2) {
      # Find runs of 3-in-a-row across the given dimension:
      # take Run Length Encoding of a row/column,
      # expand it so that runs longer than 2 get mapped to TRUE
      # e.g.: 1 2 2 2 3 3 => F T T T F F,
      # then logical OR with previous n
      n = n | apply(l, d, function(v, r=rle(v)$l)unlist(Map(rep, r>2, r)))
      # Apply always collects the results columnwise, so that
      # a transpose is necessary to make the results conformable
      n = t(n)
    }
    # If there are new matches compared to previous iteration
    if(sum(n)>sum(x))
      # Call itself recursively with the modified input l, and
      # n transposed to original shape, as new existing matches
      # The maximum of all iterations will be the final result
      F = max(F, sum(n), f(l,t(n)))
  }
  F
}