且构网

分享程序员开发的那些事...
且构网 - 分享程序员编程开发的那些事

查找阵列中的连接组件

更新时间:2023-02-26 15:15:30

好像在玩扫雷!这是我的解决方案(在Swift 4.0中,Xcode 9.2).请参阅内联注释以获取解释.

Look like you are playing Minesweeper! Here's my solution (in swift 4.0, Xcode 9.2). See inline comments for explanation.

let array = [
    "0000000000000000000",
    "0000001110000000000",
    "0000011111000000000",
    "0000001110000000000",
    "0000000000000000000",
    "0001100000000000000",
    "0001100000000011000",
    "0011100000000011000",
    "0000000000000000000"
]

// A structure to hold the cell's coordinate as Int array
// can become confusing very quickly
struct Cell: Equatable {
    var row: Int
    var column: Int
    var clusterIndex: Int?

    static func == (lhs: Cell, rhs: Cell) -> Bool {
        return lhs.row == rhs.row && lhs.column == rhs.column
    }
}

// Get all the "1" cells
var cells = array.enumerated().flatMap { arg -> [Cell] in
    let (rowIndex, str) = arg

    // The flatMap below will become compactMap in Swift 4.1
    return str.enumerated().flatMap { colIndex, char in
        if char == "1" {
            return Cell(row: rowIndex, column: colIndex, clusterIndex: nil)
        } else {
            return nil
        }
    }
}

// Assign each cell a clusterIndex
for (i, currentCell) in cells.enumerated() {

    // A cell may not have all four neighbors, or not all its
    // neighbors are "1" cells, hence the "potential"
    let potentialNeighbors = [
        Cell(row: currentCell.row - 1, column: currentCell.column, clusterIndex: nil), // above
        Cell(row: currentCell.row + 1, column: currentCell.column, clusterIndex: nil), // below
        Cell(row: currentCell.row, column: currentCell.column - 1, clusterIndex: nil), // left
        Cell(row: currentCell.row, column: currentCell.column + 1, clusterIndex: nil)  // right
    ]

    // Get the actual neighboring cells and their indexes
    let neighborsAndIndexes = cells.enumerated().filter { arg in
        let (_, c) = arg
        return potentialNeighbors.contains(c)
    }
    let neighborIndexes = neighborsAndIndexes.map { $0.0 }
    let neighbors = neighborsAndIndexes.map { $0.1 }

    // Determine what clusterIndex we should give the current cell and its neighbors
    var clusterIndex = 0

    if currentCell.clusterIndex != nil {
        // If the current cell already has a clusteredIndex, reuse it
        clusterIndex = currentCell.clusterIndex!
    } else if let neighborClusterIndex = neighbors.first(where: { $0.clusterIndex != nil })?.clusterIndex {
        // If the current cell has a neighbor whose clusterIndex is not nil, use that
        clusterIndex = neighborClusterIndex
    } else {
        // Else increment from the max existing clusterIndex
        clusterIndex = (cells.map({ $0.clusterIndex ?? 0 }).max() ?? 0) + 1
    }

    // Assign the same clusterIndex to the current cell and its neighbors
    ([i] + neighborIndexes).forEach {
        cells[$0].clusterIndex = clusterIndex
    }
}

// Group the cells by their clusterIndex
let clusters = Dictionary(grouping: cells, by: { $0.clusterIndex! })
    .sorted(by: { $0.key < $1.key })
    .map { $0.value }

// Print the result
// Visualize which cell belong to which cluster and how it appears on the board
for i in 0..<array.count {
    for j in 0..<array[0].count {
        if let clusterIndex = cells.first(where: { $0.row == i && $0.column == j })?.clusterIndex {
            print(clusterIndex, terminator: "")
        } else {
            print("-", terminator: "")
        }
    }
    print() // print a newline
}

结果:

-------------------
------111----------
-----11111---------
------111----------
-------------------
---22--------------
---22---------33---
--222---------33---
-------------------

请注意,在Swift 4.1(当前为Beta)中,我们在此处使用的flatMap已重命名为compactMap.这并不是说flatMap完全消失了. flatMap具有3个版本,其中只有1个已重命名为compactMap.有关更多信息,请参见 SE-0187 .

Note that in Swift 4.1 (currently in beta), the flatMap we use here has been renamed to compactMap. This is not to say that flatMap is going away completely. flatMap has 3 versions, only 1 of them has been renamed to compactMap. For more info, see SE-0187.