結果

問題 No.697 池の数はいくつか
ユーザー conf8oconf8o
提出日時 2020-04-30 07:04:17
言語 Swift
(5.10.0)
結果
WA  
実行時間 -
コード長 4,656 bytes
コンパイル時間 2,176 ms
コンパイル使用メモリ 191,604 KB
実行使用メモリ 25,088 KB
最終ジャッジ日時 2024-05-04 06:57:20
合計ジャッジ時間 20,900 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 11 ms
16,000 KB
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 AC 11 ms
15,616 KB
testcase_09 AC 11 ms
15,616 KB
testcase_10 WA -
testcase_11 WA -
testcase_12 AC 11 ms
15,744 KB
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 AC 11 ms
16,000 KB
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 AC 12 ms
15,872 KB
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 WA -
testcase_32 WA -
testcase_33 WA -
testcase_34 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

import Foundation

private struct Deque<T> {
    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..<n).map{(Int16) -> [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..<H {
        for j in 0..<W {
            if !A[Int(i)][Int(j)] {
                continue
            }
            ans += bfs(i, j, &A, H, W)
        }
    }
    print(ans)
}

test()
0