R 中 floodFill 算法的代码有什么问题？

Question

我从 https://rosettacode.org/wiki/Bitmap/Flood_fill 中提取了一个算法并用 R 语言对其进行了测试。添加对角线邻居匹配（如 Queeni

floodfill <- function(row, col, tcol, rcol) {
  if (tcol == rcol) return()
  if (M[row, col] != tcol) return()
  Q <- matrix(c(row, col), 1, 2)
  while (dim(Q)[1] > 0) {
    n <- Q[1, , drop = FALSE]
    west  <- cbind(n[1]    , n[2] - 1)
    east  <- cbind(n[1]    , n[2] + 1)
    north <- cbind(n[1] + 1, n[2]    )
    south <- cbind(n[1] - 1, n[2]    )
    nwest  <- cbind(n[1] - 1, n[2] - 1)
    neast  <- cbind(n[1] - 1, n[2] + 1)
    swest  <- cbind(n[1] + 1, n[2] - 1)
    seast  <- cbind(n[1] + 1, n[2] + 1)
    Q <- Q[-1, , drop = FALSE]
    if (M[n] == tcol) {
      M[n] <<- rcol
      if (M[west] == tcol)  Q <- rbind(Q, west)
      if (M[east] == tcol)  Q <- rbind(Q, east)
      if (M[north] == tcol) Q <- rbind(Q, north)
      if (M[south] == tcol) Q <- rbind(Q, south)
      if (M[nwest] == tcol)  Q <- rbind(Q, nwest)
      if (M[neast] == tcol)  Q <- rbind(Q, neast)
      if (M[swest] == tcol)  Q <- rbind(Q, swest)
      if (M[seast] == tcol)  Q <- rbind(Q, seast)
    }
  }
  return("filling completed")
}

我不确定哪里做错了。我收到这样的执行错误：

一个矩阵：

M = matrix(c(c(1,0,0,0,0,0,0,1),
             c(0,1,0,0,0,1,1,0),
             c(0,0,1,1,1,1,1,0),
             c(0,0,0,0,1,1,0,0),
             c(0,0,0,0,0,1,0,1),
             c(0,0,0,1,0,1,0,1)), nrow = 6, byrow = T)

一个电话：

> floodfill(row=3, col=3, tcol=1, rcol=2)
Error in if (M[west] == tcol) Q <- rbind(Q, west) : 
  argument is of length zero

从 (3,3) 开始填充，但填充在第 6 列某处停止，其余部分未替换为 2s。是我的修改错误还是Rosetta代码？

Answer 1

rosetta stone 上提供的"solution" 不对数组进行任何边界检查。这是一个替代方案

floodfill <- function(row, col, tcol, rcol) {
  if (tcol == rcol) return()
  if (M[row, col] != tcol) return()
  Q <- matrix(c(row, col), 1, 2)
  moves <- matrix(c(-1, 0, 1, -1, 1, -1, 0, 1,
                    -1, -1, -1, 0, 0, 1, 1, 1), ncol=2)
  check <- function(p) {
    if(p[,1] >= 1 & p[,1] <= nrow(M) & p[,2] >= 1 & p[,2] <= ncol(M)) {
      if (M[p] == tcol)  
        Q <<- rbind(Q, p)
    }
  }
  while (dim(Q)[1] > 0) {
    n <- Q[1, , drop = FALSE]
    dirs <- cbind(n[1] + moves[,1], n[2] + moves[,2])
    Q <- Q[-1, , drop = FALSE]
    if (M[n] == tcol) {
      M[n] <<- rcol
      for(i in seq.int(nrow(dirs)))
        check(dirs[i, , drop=FALSE])
    }
  }
  return("filling completed")
}

R 中 floodFill 算法的代码有什么问题？

What's wrong with the code for floodFill algorithm in R?

algorithm

queue

r

flood-fill