Как я могу изменить свой рекурсивный код для подключения всех плиток, не пересекая плитку более одного раза? - PullRequest
Новая
       45

Как я могу изменить свой рекурсивный код для подключения всех плиток, не пересекая плитку более одного раза?

1 голос
/ 08 марта 2019

Вот иллюстрация того, что я пытаюсь заставить сделать мой код Swift:

enter image description here

Я пометил плитки цифрами. Плитка 3 и 8 отключена. 6 является отправной точкой, а 0 - целью.

ПРИМЕЧАНИЕ: Начальная точка указана, а конечная точка - нет. Конечная точка может быть любой, если путь проходит через все плитки. В моем примере я просто указал 0, чтобы упростить его, но на самом деле он не будет указан.

Мне разрешено идти только горизонтально или вертикально. Есть несколько способов добраться до цели, но мне нужно найти путь, который проходит через все числа один раз. Я отметил этот путь на изображении (6,7,4,5,2,1,0).

Прямо сейчас у меня есть следующий код, который сначала получает все прямые соединения каждой плитки, а затем использует рекурсию, чтобы найти путь. В настоящее время мой код дает мне путь 6,7,4,1,0, который не проходит через 5 и 2 и, следовательно, не то, что я хочу.

Я не уверен, как изменить свой код, чтобы получить путь, который проходит через все плитки. 

let size = (rows: 3, columns: 3)
let off = [3,8]
let start : Int = 6
let finish : Int = 0
var connections = [Int:[Int]]()
var path = [Int]()
var visited = [Int]()

func backtrackingStuff() {

    for index in 0..<size.rows * size.columns {
        if !off.contains(index) {

            let rowStart : Int = index - index%size.columns
            let rowEnd : Int = rowStart + size.columns - 1

            var temp = [Int]()
            let possibleUpperConnection : Int = index - size.columns
            if possibleUpperConnection >= 0 && !off.contains(possibleUpperConnection) {
                temp.append(possibleUpperConnection)
            }
            let possibleBottomConnection : Int = index + size.columns
            if possibleBottomConnection <= (size.rows * size.columns - 1) && !off.contains(possibleBottomConnection) {
                temp.append(possibleBottomConnection)
            }

            let possibleLeftConnection : Int = index - 1
            if possibleLeftConnection >= rowStart && !off.contains(possibleLeftConnection) {
                temp.append(possibleLeftConnection)
            }

            let possibleRightConnection : Int = index + 1
            if possibleRightConnection <= rowEnd && !off.contains(possibleRightConnection) {
                temp.append(possibleRightConnection)
            }

            connections[index] = temp
        }
    }

    print("V: \(NSSet(array: Array(connections.keys)))")

    getPaths(currentPosition: start)

    print("Path: \(path)")
}

func getPaths (currentPosition : Int) -> Bool {

    //if NSSet(array: possiblePath).isEqual(to: NSSet(array: Array(connections.keys)) as! Set<AnyHashable>) { {
    if currentPosition == finish {
        path.insert(currentPosition, at: 0)
        return true
    }

    visited.append(currentPosition)

    if let connectionsForThisIndex = connections[currentPosition] {
        for newIndex in connectionsForThisIndex {
            if !visited.contains(newIndex) {
                if getPaths(currentPosition: newIndex) {
                    path.insert(currentPosition, at: 0)
                    return true
                }
            }
        }
    }

    return false
}
...