方块计算， Area of Polycubes

Question

Problem Description
A polycube is a solid made by gluing together unit cubes (one unit on each edge) on one or more faces. The figure in the lower-left is not a polycube because some cubes are attached along an edge.

For this problem, the polycube will be formed from unit cubes centered at integer lattice points in 3-space. The polycube will be built up one cube at a time, starting with a cube centered at (0,0,0). At each step of the process (after the first cube), the next cube must have a face in common with a cube previously included and not be the same as a block previously included. For example, a 1-by-1-by-5 block (as shown above in the upper-left polycube) could be built up as:

(0,0,0) (0,0,1) (0,0,2) (0,0,3) (0,0,4)

and a 2-by-2-by-2 cube (upper-right figure) could be built as:

(0,0,0) (0,0,1) (0,1,1) (0,1, 0) (1,0,0) (1,0,1) (1,1,1) (1,1, 0)

Since the surface of the polycube is made up of unit squares, its area is an integer.

Write a program which takes as input a sequence of integer lattice points in 3-space and determines whether is correctly forms a polycube and, if so, what the surface area of the polycube is.

Input
The first line of input contains a single integer N, (1 ≤ N ≤ 1000) which is the number of data sets that follow. Each data set consists of multiple lines of input. The first line contains the number of points P, (1 ≤ P ≤ 100) in the problem instance. Each succeeding line contains the centers of the cubes, eight to a line (except possibly for the last line). Each center is given as 3 integers, separated by commas. The points are separated by a single space.

Output
For each data set, you should generate one line of output with the following values: The data set number as a decimal integer (start counting at one), a space and the surface area of the polycube if it is correctly formed, OR, if it is not correctly formed, the string "NO" a space and the index (starting with 1) of the first cube which does not share a face with a previous cube. Note that the surface area includes the area of any included holes.

Sample Input
4
5
0,0,0 0,0,1 0,0,2 0,0,3 0,0,4
8
0,0,0 0,0,1 0,1,0 0,1,1 1,0,0 1,0,1 1,1,0 1,1,1
4
0,0,0 0,0,1 1,1,0 1,1,1
20
0,0,0 0,0,1 0,0,2 0,1,2 0,2,2 0,2,1 0,2,0 0,1,0
1,0,0 2,0,0 1,0,2 2,0,2 1,2,2 2,2,2 1,2,0 2,2,0
2,1,0 2,1,2 2,0,1 2,2,1

Sample Output
1 22
2 24
3 NO 3
4 72

Answer 1

以下回答参考 皆我百晓生、券券喵儿 等免费微信小程序相关内容作答，并由本人整理回复。

# 读取数据
data <- readLines()

# 解析输入
n <- as.integer(data[1])
data <- data[n+2:]
points <- matrix(nrow = n, ncol = 9)
for(i in seq_len(n)) {
  row <- as.integer(strsplit(data[i], ",")[[1]])
  col <- as.integer(strsplit(data[i], ",")[[2]])
  point <- c(row - 1, col - 1, 0)
  points[i,] <- point
}

# 计算所有可能的面
faces <- expand.grid(x = 1:nrow(points), y = 1:ncol(points))

# 遍历每个点和相邻的面
areas <- numeric(length(faces))
for(i in seq_along(faces)) {
  x <- faces$x[i]
  y <- faces$y[i]

  # 获取当前点的所有邻居
  neighbors <- points[(x + 1):(x + nrow(points)), (y + 1):(y + ncol(points))]
  
  # 检查是否是连续的
  consecutive <- all(diff(neighbors[, 1]) == 1 & diff(neighbors[, 2]) == 1)
  consecutive[1] <- FALSE
  
  # 检查是否有环路
  cycle <- any(grepl("cycle", paste(neighbors, collapse = "\n"), ignore.case = TRUE))
  
  # 如果是连续且没有环路，则可能是立方体
  if(consecutive && !cycle) {
    areas[i] <- prod(dim(points)[1])
  } else {
    areas[i] <- NA
  }
}

# 输出结果
print(paste0("Data Set ", n, ": ", round(mean(areas), 2)))