gpt4 book ai didi

algorithm - Swift 递归回溯算法不工作

转载 作者:塔克拉玛干 更新时间:2023-11-03 05:22:39 24 4
gpt4 key购买 nike

您好,我用 swift 编写了一个类,它应该通过递归回溯算法创建一个迷宫。我似乎对迷宫的墙壁分配有疑问。但我无法破解它。

如果能在这里得到一些帮助就太好了,谢谢!

请在下面找到代码的说明

2D Array 类 - 不言自明。给它一些列和行以及一个默认值,它从那里生成二维数组。下标方法允许您设置和获取值。

class Array2D<T> {
let columns: Int
let rows: Int
var array : Array<Array<T?>>

init(columns: Int, rows: Int, repeatedValue: T?) {
self.columns = columns
self.rows = rows
var tmp = Array<T?>(count: rows, repeatedValue: repeatedValue)
array = Array<Array<T?>>(count: columns, repeatedValue: tmp)
}

subscript(column: Int, row: Int) -> T? {
get {
return array[column][row]
}
set(newValue) {
array[column][row] = newValue
}
}
}

DIR enum 一个枚举,它允许我们通过为它们分配名称来从位中抽象出我们自己。

enum DIR : UInt8 {
case N = 1
case S = 2
case E = 4
case W = 8
case O = 0
}

Direction 类 这个类包含有关 Directions 的所有信息。这可能有点矫枉过正。它允许您获取与当前位置相关的方向(N、S、E、W)。你也可以得到相反的方向。

class Direction {
var bit : DIR
var dx : Int
var dy : Int

init(bit: DIR, dx: Int, dy: Int) {
self.bit = bit
self.dx = dx
self.dy = dy
}

class func NORTH() -> Direction {
return Direction(bit: DIR.N, dx: 0, dy: -1)
}

class func SOUTH() -> Direction {
return Direction(bit: DIR.S, dx: 0, dy: 1)
}

class func EAST() -> Direction {
return Direction(bit: DIR.E, dx: 1, dy: 0)
}

class func WEST() -> Direction {
return Direction(bit: DIR.W, dx: -1, dy: 0)
}

func opposite() -> Direction {
switch(bit){
case DIR.N:
return Direction.SOUTH()
case DIR.S:
return Direction.NORTH()
case DIR.E:
return Direction.WEST()
case DIR.W:
return Direction.EAST()
default:
println("An error occured while returning the opposite of the direction with bit: \(bit)")
return Direction(bit: DIR.O, dx: 0, dy: 0)
}
}
}

RecursiveBackTracking 类 这就是魔法发生的地方。此类自动生成给定宽度(x)和高度(y)的迷宫。 generateMaze() 函数与支持的其他函数一起完成大部分工作。这里的一切似乎都有效,但我仍然没有得到适当的结果。潜在的问题也可能出在 display() 函数中。

class RecursiveBacktracking {
var x : Int
var y : Int
var maze : Array2D<UInt8>

init(x: Int, y: Int) {
self.x = x
self.y = y
maze = Array2D<UInt8>(columns: x, rows: y, repeatedValue: 0)
generateMaze(0, cy: 0)
display()
}

func generateMaze(cx: Int, cy: Int) {
var directions : [Direction] = [Direction.NORTH(),Direction.SOUTH(),Direction.EAST(),Direction.WEST()]
directions = shuffle(directions)

for dir in directions {
var nx : Int = cx + dir.dx
var ny : Int = cx + dir.dy

if between(nx, upper: x) && between(ny, upper: y) && getMazeObject(nx, y: ny) == 0 {
maze[cx,cy] = bitwiseOr(getMazeObject(cx, y: cy), b: dir.bit.rawValue)
maze[nx,ny] = bitwiseOr(getMazeObject(nx, y: ny), b: dir.opposite().bit.rawValue)
generateMaze(nx, cy: ny)
}
}
}

func bitwiseOr(a: UInt8, b: UInt8) -> UInt8 {
return a | b
}

func getMazeObject(x: Int, y: Int) -> UInt8 {
if var object = maze[x,y] {
return object
}else{
println("No object could be found at location: (\(x),\(y)).")
return 0
}
}

func between(v: Int, upper: Int) -> Bool {
return (v>=0) && (v<upper)
}

func shuffle<C: MutableCollectionType where C.Index == Int>(var list: C) -> C {
let count : Int = Int(countElements(list))
for i in 0..<(count - 1) {
let j = Int(arc4random_uniform(UInt32(count - i))) + i
swap(&list[i], &list[j])
}
return list
}

func display() {
for i in 0..<y {
// Draw North Edge
for j in 0..<x {
var bit : UInt8 = getMazeObject(j, y: i)
bit = bit & 1
if bit == 0 {
print("+---")
}else{
print("+ ")
}
}
println("+")

// Draw West Edge
for j in 0..<x {
var bit : UInt8 = getMazeObject(j, y: i)
bit = bit & 8
if bit == 0 {
print("| ")
}else{
print(" ")
}
}
println("|")
}

// Draw the bottom line
for j in 0..<x {
print("+---")
}
println("+")
}
}

附加信息:该算法基于 http://rosettacode.org/wiki/Maze#Java

最佳答案

错误在这里:

var nx : Int = cx + dir.dx
var ny : Int = cx + dir.dy

第二个cx应该是cy

备注:您的代码还有一些改进空间。例如,bitwise 或 | 已经为 UInt8 定义,因此无需定义作为一个功能。如果您已修复代码以使其正常工作,您可能会考虑将其张贴在 http://codereview.stackexchange.com获得评论。

关于algorithm - Swift 递归回溯算法不工作,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/27398917/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com