Swift: как более точно определить, находится ли символ внутри или снаружи стены?

Question

Карта рисуется с текстовым содержимым, как показано ниже:

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

#: стена

.: пусто (используйте @ в качестве специального . сверху )

Поскольку существует два вида заготовок, внутри и снаружи стены. Мне нужно выяснить их отдельно.

Внутреннее . преобразуется в 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
                }
            }
        }

Это может быть не эффективен, и это нормально в большинстве случаев, за исключением одного случая, когда он неэффективен: из карты выше видно, что @ находится внутри стены. Поскольку он имеет # в четырех направлениях, но на самом деле он стоит за стеной.

Как улучшить приведенный выше код более эффективным и точным?

Спасибо.

Answer 1

Идея

Мы можем построить рекурсивную функцию для поиска пути от героя до границы.

Если такой путь существует , тогда герой снаружи стен. В противном случае он внутри стен.

Рекурсивная функция получает cell index в качестве параметра вместе с набором посещенных индексов.

Если эта ячейка находится на border , тогда функция возвращает true. В противном случае он оценивает все смежные ячейки с текущей, которые свободны и не были посещены .

Для каждой из этих ячеек функция называется рекурсивно до тех пор, пока не будет найден путь к границе или пока не будут посещены все ячейки.

Код!

Нам необходим правильный способ представления и взаимодействия с картой.

Я собираюсь использовать структуру Matrix, описанную в Язык программирования Swift , и добавлю некоторые настройки.

Матрица ?

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

Надеюсь, это поможет.