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

Submission #1141010

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(H, W, K, table)

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

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得点 216548
Source lengthソースコード長 1884 Byte
File nameファイル名
Exec time実行時間 34 ms
Memory usageメモリ使用量 3828 KB

Test case

Set

Set name Score得点 / Max score Cases
test_01 22407 / 1343058 subtask_01_01.txt
test_02 19478 / 1343058 subtask_01_02.txt
test_03 22600 / 1343058 subtask_01_03.txt
test_04 20506 / 1343058 subtask_01_04.txt
test_05 21124 / 1343058 subtask_01_05.txt
test_06 21894 / 1343058 subtask_01_06.txt
test_07 25148 / 1343058 subtask_01_07.txt
test_08 21414 / 1343058 subtask_01_08.txt
test_09 21094 / 1343058 subtask_01_09.txt
test_10 20883 / 1343058 subtask_01_10.txt

Test case

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