时间戳

首页 > 解决方案 > Swift：如何更准确地检测符号是在墙内还是墙外？

swift - Swift：如何更准确地检测符号是在墙内还是墙外？

问题描述

使用如下文本内容绘制地图：

#######..
#.....#..
#...#####
#...#@..#
#...##..#
#....#...
######...

#： 墙

.：空白（在上面@用作特殊.）

由于有两种坯料，内墙和外墙。我需要单独弄清楚它们。

内部.将转换为 2，外部.将转换为 0

到目前为止，我正在使用一种方法来搜索每个点的四个方向（上、下、左、右），如果它们都是#，则该点在墙内。

首先，将每一行转换为数组lines

var wallCount = 0
        for i in 0...lines.count{
            let line = lines[i]

            // ignore first and last character
            for  j in 1...line.count-2 {

                let char = String(Array(line)[j])
                if char == "." {
                    var wallCount = 0
                    // left
                    var l = j
                    while (l >= 0) {
                        let lChar = String(Array(line)[l])
                        if(lChar == "#"){
                            wallCount += 1
                            break;
                        }
                        l -= 1
                    }

                    // and then...
                    // right
                    // up
                    // down
                }
            }
        }

它可能效率不高，在大多数情况下都可以，除了在一种情况下无效：从上面的地图来看，它显示@在墙内。因为它有#四个方向，但实际上它是站在墙外的。

如何更高效、更准确地改进上述代码？

谢谢。

标签： swiftio

解决方案

这个想法

我们可以构建一个递归函数来寻找从英雄到边界的路径。

如果存在这样的路径，那么英雄就在墙外。否则他在墙内。

递归函数接收 acell index作为参数以及访问索引的集合。

如果此单元格在边界上，则函数返回true。否则，它会评估与当前空闲且未被访问过的所有单元格相邻的所有单元格。

对于这些单元格中的每一个，该函数被递归调用，直到找到通往边界的路径或所有单元格都已被访问。

代码！

我们需要一种正确的方式来表示 Map 并与之交互。

我将使用Swift 编程语言中描述的 Matrix 结构并添加一些自定义。

矩阵

struct Matrix {

    enum Cell: String {
        case wall = "#"
        case empty = "."
        case hero = "@"
    }

    struct Index: Hashable {
        let x, y: Int

        var adjacents: [Index] {
            return [Index(x: x - 1, y: y), Index(x: x + 1, y: y), Index(x: x, y: y - 1), Index(x: x, y: y + 1)]
        }
    }

    private let rows: Int, columns: Int
    private var grid: [Cell]

    init(rows: Int, columns: Int) {
        self.rows = rows
        self.columns = columns
        grid = Array(repeating: .empty, count: rows * columns)
    }

    private func indexIsValid(index: Index) -> Bool {
        return indexIsValid(row: index.x, column: index.y)
    }

    private func indexIsValid(row: Int, column: Int) -> Bool {
        return row >= 0 && row < rows && column >= 0 && column < columns
    }

    subscript(row: Int, column: Int) -> Cell {
        get {
            assert(indexIsValid(row: row, column: column), "Index out of range")
            return grid[(row * columns) + column]
        }
        set {
            assert(indexIsValid(row: row, column: column), "Index out of range")
            grid[(row * columns) + column] = newValue
        }
    }

    var description: String {
        var res = ""
        for row in 0..<rows {
            for column in 0..<columns {
                res += self[row, column].rawValue
            }
            res += "\n"
        }
        return res
    }

    private func indexIsOnBorder(_ index: Index) -> Bool {
        return index.x == 0 || index.y == 0 || index.x == columns - 1 || index.y == rows - 1
    }

    func findPathToBorder(from index: Index,
                          visitedIndexes: inout Set<Index>) -> Bool {

        visitedIndexes.insert(index)
        if matrix.indexIsOnBorder(index) {
            return true
        }
        return index
            .adjacents // up, right, down, left
            .filter(indexIsValid) // which are inside the matrix
            .filter { matrix[$0.x, $0.y] == .empty } // are empty
            .filter { !visitedIndexes.contains($0) } // not visited yet
            .contains { adjacent in
                findPathToBorder(from: adjacent, visitedIndexes: &visitedIndexes)
            } // and are part of a path to the border
    }

}

填充矩阵

var matrix = Matrix(rows: 7, columns: 9)
matrix[0, 0] = .wall
matrix[0, 1] = .wall
matrix[0, 2] = .wall
matrix[0, 3] = .wall
matrix[0, 4] = .wall
matrix[0, 5] = .wall
matrix[0, 6] = .wall

matrix[1, 0] = .wall
matrix[1, 6] = .wall

matrix[2, 0] = .wall
matrix[2, 4] = .wall
matrix[2, 5] = .wall
matrix[2, 6] = .wall
matrix[2, 7] = .wall
matrix[2, 8] = .wall

matrix[3, 0] = .wall
matrix[3, 4] = .wall
matrix[3, 5] = .hero
matrix[3, 8] = .wall

matrix[4, 0] = .wall
matrix[4, 4] = .wall
matrix[4, 5] = .wall
matrix[4, 8] = .wall

matrix[5, 0] = .wall
matrix[5, 5] = .wall

matrix[6, 0] = .wall
matrix[6, 1] = .wall
matrix[6, 2] = .wall
matrix[6, 3] = .wall
matrix[6, 4] = .wall
matrix[6, 5] = .wall

print(matrix.description)

现在您将在控制台中看到它

#######..
#.....#..
#...#####
#...#@..#
#...##..#
#....#...
######...

运行我们的函数

var visitedIndexes: Set<Matrix.Index> = []
let isHeroOutsideTheWalls = matrix.findPathToBorder(from: Matrix.Index(x: 3, y: 2), visitedIndexes: &visitedIndexes)

print(isHeroOutsideTheWalls) // true

希望这可以帮助。

推荐阅读