import Foundation private struct Deque { private var buffer: [T?] = [T?](repeating: nil, count: 8) private var head: Int private var tail: Int init() { head = 0 tail = 0 } public var isEmpty: Bool { return tail == head } public var capacity: Int { return buffer.capacity } public var count: Int { return (head &- tail) & (capacity - 1) } public var isFull: Bool { return capacity - count == 1 } private func wrapIndex(index: Int, size: Int) -> Int { return index & (size - 1) } private func wrapAdd(index: Int, append: Int) -> Int { return wrapIndex(index: index &+ append, size: capacity) } private func wrapSub(index: Int, subtrahend: Int) -> Int { return wrapIndex(index: index &- subtrahend, size: capacity) } mutating func growIfNecessary() { if isFull { let oldCap = capacity buffer.append(contentsOf: Array(repeating: nil, count: capacity)) handleCapacityIncrease(oldCap: oldCap) } } private mutating func handleCapacityIncrease(oldCap: Int) { let newCap = capacity // T H // [ooooooo.] // T H // [ooooooo.........] if tail <= head { } // HT // [oo.ooooo] // T H // [...ooooooo......] else if head < oldCap - tail { buffer.withUnsafeMutableBufferPointer { bufPointer in let _buffer = bufPointer.baseAddress! for i in 0...head { swap(&_buffer[i], &_buffer[i+oldCap]) } } head += oldCap } // HT // [ooooo.oo] // H T // [ooooo.........oo] else { let newTail = newCap - (oldCap - tail) buffer.withUnsafeMutableBufferPointer { bufPointer in let _buffer = bufPointer.baseAddress! for i in tail...(oldCap - tail) { swap(&_buffer[i], &_buffer[i+newTail]) } } } } public mutating func pushBack(_ element: T) { growIfNecessary() let head = self.head self.head = wrapAdd(index: self.head, append: 1) buffer[head] = element } public mutating func pushFront(_ element: T) { growIfNecessary() self.tail = wrapSub(index: self.tail, subtrahend: 1) let tail = self.tail buffer[tail] = element } mutating func popBack() -> T? { if isEmpty { return nil } else { self.head = wrapSub(index: self.head, subtrahend: 1) let head = self.head return buffer[head] } } mutating func popFront() -> T? { if isEmpty { return nil } else { let tail = self.tail self.tail = wrapAdd(index: self.tail, append: 1) return buffer[tail] } } func peekFront() -> T? { if isEmpty { return nil } else { return buffer[head] } } func peekBack() -> T? { if isEmpty { return nil } else { return buffer[tail] } } } func readInt2() -> (Int16, Int16) { let l = readLine()!.split(separator: " ").map{Int16($0)!} return (l[0], l[1]) } func readLines(_ n: Int16) -> [[Bool]] { return (0.. [Bool] in return readLine()!.split(separator: " ").map{$0 == "1"} } } func bfs(_ i: Int16, _ j: Int16, _ grid: inout [[Bool]], _ H: Int16, _ W: Int16) -> Int{ var frontier = Deque<(Int16, Int16)>() frontier.pushBack((i, j)) let dires: [(Int16, Int16)] = [(-1, 0),(0, 1),(1, 0),(0, -1)] while !frontier.isEmpty { let (h, w) = frontier.popFront()! grid[Int(h)][Int(w)] = false for (y, x) in dires { let sucY = h+y let sucX = w+x if sucY < 0 || sucY >= H || sucX < 0 || sucX >= W || !grid[Int(sucY)][Int(sucX)] { continue } frontier.pushBack((sucY, sucX)) } } return 1 } func test() { let (H, W): (Int16, Int16) = readInt2() var A = readLines(H) var ans = 0 for i in 0..