90 lines
2.4 KiB
Swift
90 lines
2.4 KiB
Swift
public struct Deque<T> {
|
|
private var front: [T] = []
|
|
private var back: [T] = []
|
|
|
|
public var isEmpty: Bool {
|
|
return front.isEmpty && back.isEmpty
|
|
}
|
|
|
|
public var count: Int {
|
|
return front.count + back.count
|
|
}
|
|
|
|
public mutating func append(_ element: T) {
|
|
back.append(element)
|
|
}
|
|
|
|
public mutating func prepend(_ element: T) {
|
|
front.append(element)
|
|
}
|
|
|
|
public mutating func popFirst() -> T? {
|
|
if front.isEmpty {
|
|
front = back.reversed()
|
|
back.removeAll()
|
|
}
|
|
return front.popLast()
|
|
}
|
|
|
|
public mutating func popLast() -> T? {
|
|
if back.isEmpty {
|
|
back = front.reversed()
|
|
front.removeAll()
|
|
}
|
|
return back.popLast()
|
|
}
|
|
}
|
|
|
|
if let input = readLine(),
|
|
let nm = {
|
|
let numList = input.split(separator : " ").compactMap({Int($0)})
|
|
return numList.count==2 ? numList : nil
|
|
}() as [Int]? {
|
|
let N = nm[0]
|
|
let M = nm[1]
|
|
var q: Deque<(Int, Int)> = Deque()
|
|
var snake_ladder: [Int: Int] = Dictionary(uniqueKeysWithValues: zip(1...100, 1...100))
|
|
var visited: [Bool] = Array(repeating: false, count: 101)
|
|
|
|
for _ in 0..<N+M {
|
|
if let line = readLine(),
|
|
let uv = {
|
|
let numList = line.split(separator: " ").compactMap({Int($0)})
|
|
return numList.count==2 ? numList : nil
|
|
}() as [Int]? {
|
|
snake_ladder[uv[0]] = uv[1]
|
|
}
|
|
else {
|
|
print("error U, V or X, Y")
|
|
}
|
|
}
|
|
|
|
var current, dice : Int
|
|
q.append((1,0))
|
|
visited[1] = true
|
|
while q.count != 0 {
|
|
if let currentTuple = q.popFirst() {
|
|
current = currentTuple.0
|
|
dice = currentTuple.1
|
|
if current == 100 {
|
|
print(dice )
|
|
break
|
|
}
|
|
for n in 1...6 {
|
|
if current + n <= 100, !visited[current+n], let next = snake_ladder[current + n] {
|
|
q.append((next, dice + 1))
|
|
visited[next] = true
|
|
}
|
|
else {
|
|
continue
|
|
}
|
|
}
|
|
}
|
|
else {
|
|
continue
|
|
}
|
|
}
|
|
}
|
|
else {
|
|
print("error N, M")
|
|
} |