javascript - 给出给定字符串数组所需的最小笔画的函数

Question

它被赋予一个字符串数组。字符串具有相同的长度。假设输入数组是 (["ababc", "abbba", "aaabb", "bcccb", "acbbb", "aaabb"]).

a b a b c
a b b b a
a a a b b
b c c c b
a c b b b
a a a b b

问题是关于找到最小的字母连接组，可以垂直和水平地绘制同一个字母，但不能沿对 Angular 线绘制。对于此示例，字母“a”有 4 个组(两个单组，两个多组)，字母“b”分为 2 组(一个单一的，一个多重的)和字母“c”的 2 个组(一个单一的，一个多重的)。所以，输出应该是“8”。我找不到使用 JavaScript 的解决方案。

我试图将其视为单独的行和列。此外，为每个字符创建数组并单独分析。但它们都无法正常工作。

function strokesRequired(picture){
        let total = picture.join('');
        let strLength = picture[0].length;
        let counter = 0;
        for(let i = 0; i < total.length; i++){
          if(total[i] !== total[i+1] || total[i] !== total[i+strLength] || total[i] !== total[i-1] || total[i] !== total[i-strLength]){
            continue;
         }
         else {        
            counter++;
          }      
        }
        return counter;    
      }

对于这个问题，我的代码返回 4，但应该返回 8。因为我只是计算字母，没有任何水平和垂直匹配。

Answer 1

这是从每个未访问过的单元格运行深度优先搜索的一种方法。我认为这也可以通过泛洪填充来解决，即在显示连接时合并组件标签。

function f(M){
  let m = M.length
  let n = M[0].length
  let visited = new Array(m)
  for (let i=0; i<m; i++)
    visited[i] = new Array(n).fill(0)
    
  function getNeighbours(y, x){
    let c = M[y][x]
    let neighbours = []

    if (y > 0 && !visited[y-1][x] && M[y-1][x] == c)
      neighbours.push([y-1, x])
    if (y < m - 1 && !visited[y+1][x] && M[y+1][x] == c)
      neighbours.push([y+1, x])
    if (x > 0 && !visited[y][x-1] && M[y][x-1] == c)
      neighbours.push([y, x-1])
    if (x < n - 1 && !visited[y][x+1] && M[y][x+1] == c)
      neighbours.push([y, x+1])

    return neighbours
  }
    
  function dfs(y, x){
    let stack = [[y, x]]
  
    while (stack.length){
      let [y, x] = stack.pop()
      visited[y][x] = 1
      stack.push(...getNeighbours(y, x))
    }
  }
  
  let count = 0
  
  for (let i=0; i<m; i++){
    for (let j=0; j<n; j++){
      if (!visited[i][j]){
        count++
        dfs(i, j)
      }
    }
  }
  
  return count
}

var M = [
  "ababc",
  "abbba",
  "aaabb",
  "bcccb",
  "acbbb",
  "aaabb"
]

console.log(f(M))