結果

問題 No.697 池の数はいくつか
ユーザー conf8oconf8o
提出日時 2020-04-30 07:44:39
言語 Swift
(5.10.0)
結果
WA  
実行時間 -
コード長 4,588 bytes
コンパイル時間 13,158 ms
コンパイル使用メモリ 190,528 KB
実行使用メモリ 16,000 KB
最終ジャッジ日時 2024-05-04 06:56:49
合計ジャッジ時間 20,343 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

import Foundation

private struct Deque<T> {
    public 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.count
    }
    
    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 {
            print(capacity, count)
            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 { buf in
                for i in 0...head {
                    buf.swapAt(i, i+oldCap)
                }
            }
            head += oldCap
        }
        //       HT
        // [ooooo.oo]
        //       H        T
        // [ooooo.........oo]
        else {
            let newTail = newCap - (oldCap - tail)
            print(buffer)
            buffer.withUnsafeMutableBufferPointer { buf in
                for i in tail..<oldCap {
                    buf.swapAt(i, (i-tail)+newTail)
                }
            }
            tail = 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