RCO presents 日本橋ハーフマラソン 予選

Submission #1142583

Source codeソースコード

import sys
from heapq import heapify, heappush, heappop

def solve():
    # Input
    H, W, K = map(int, input().split())
    table = [[int(j) for j in input()] for i in range(H)]

    # Process
    c, ans = tekito_connect_kai(H, W, K, table)

    # Output
    print(c)
    for i in range(c):
        for con in ans[i]:
            print(*con)

def tekito_connect_kai(H, W, K, table):
    dx = [1, 0, -1, 0,]
    dy = [0, 1, 0, -1,]
    used = [[False] * W for i in range(H)]
    res = []
    ndhp = []

    for i in range(H):
        for j in range(W):
            if table[i][j] != 0:
                heappush(ndhp, (-table[i][j], i, j))

    # debug(ndhp, locals())

    while ndhp:
        val, a, b = heappop(ndhp)

        if used[a][b]:
            continue

        mxhp = []
        ch = set([(a, b)])
        ck = [(a + 1, b + 1)]
        flag = dfs(H, W, K, a, b, table, used, mxhp, ck, ch)

        if flag:
            res.append(ck)

    return len(res), res


def tekito_connect(H, W, K, table):
    dx = [1, 0, -1, 0,]
    dy = [0, 1, 0, -1,]
    used = [[False] * W for i in range(H)]
    res = []

    for i in range(H):
        for j in range(W):
            if table[i][j] and not used[i][j]:
                mxhp = []
                ch = set([(i, j)])
                ck = [(i+1, j+1)]
                value = dfs(H, W, K, i, j, table, used, mxhp, ck, ch)
                if value:
                    res.append(ck)

    return len(res), res

def dfs(H, W, K, i, j, table, used, mxhp, ck, ch):
    if len(ck) == K:
        for a, b in ck:
            used[a-1][b-1] = True

        return True

    dx = [1, 0, -1, 0,]
    dy = [0, 1, 0, -1,]

    for t in range(4):
        if (0 <= i + dx[t] < H and 0 <= j + dy[t] < W
            and table[i + dx[t]][j + dy[t]]
            and (not used[i + dx[t]][j + dy[t]])
            and (i + dx[t], j + dy[t]) not in ch):

            heappush(mxhp, (-table[i + dx[t]][j + dy[t]], i + dx[t], j + dy[t]))
            ch.add((i + dx[t], j + dy[t]))

    if (not mxhp) or mxhp[0][0] == 0:
        return False
    else:
        v, a, b = heappop(mxhp)
        used[a][b] = True
        ck.append((a + 1, b + 1))
        return dfs(H, W, K, a, b, table, used, mxhp, ck, ch)

def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

if __name__ == '__main__':
    solve()

Submission

Task問題 A - Multiple Pieces
User nameユーザ名 nanae
Created time投稿日時
Language言語 Python3 (3.4.3)
Status状態 AC
Score得点 783413
Source lengthソースコード長 2549 Byte
File nameファイル名
Exec time実行時間 36 ms
Memory usageメモリ使用量 4084 KB

Test case

Set

Set name Score得点 / Max score Cases
test_01 78803 / 1343058 subtask_01_01.txt
test_02 71457 / 1343058 subtask_01_02.txt
test_03 82773 / 1343058 subtask_01_03.txt
test_04 73882 / 1343058 subtask_01_04.txt
test_05 87893 / 1343058 subtask_01_05.txt
test_06 74781 / 1343058 subtask_01_06.txt
test_07 79915 / 1343058 subtask_01_07.txt
test_08 71915 / 1343058 subtask_01_08.txt
test_09 80835 / 1343058 subtask_01_09.txt
test_10 81159 / 1343058 subtask_01_10.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
subtask_01_01.txt AC 36 ms 4084 KB
subtask_01_02.txt AC 36 ms 4084 KB
subtask_01_03.txt AC 36 ms 4084 KB
subtask_01_04.txt AC 35 ms 4084 KB
subtask_01_05.txt AC 34 ms 4084 KB
subtask_01_06.txt AC 34 ms 4084 KB
subtask_01_07.txt AC 34 ms 4084 KB
subtask_01_08.txt AC 34 ms 4084 KB
subtask_01_09.txt AC 35 ms 4084 KB
subtask_01_10.txt AC 34 ms 4084 KB