Submission #1142583


Source Code Expand

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 Info

Submission Time
Task A - Multiple Pieces
User nanae
Language Python (3.4.3)
Score 783413
Code Size 2549 Byte
Status AC
Exec Time 36 ms
Memory 4084 KB

Judge Result

Set Name test_01 test_02 test_03 test_04 test_05 test_06 test_07 test_08 test_09 test_10
Score / Max Score 78803 / 1343058 71457 / 1343058 82773 / 1343058 73882 / 1343058 87893 / 1343058 74781 / 1343058 79915 / 1343058 71915 / 1343058 80835 / 1343058 81159 / 1343058
Status
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
Set Name Test Cases
test_01 subtask_01_01.txt
test_02 subtask_01_02.txt
test_03 subtask_01_03.txt
test_04 subtask_01_04.txt
test_05 subtask_01_05.txt
test_06 subtask_01_06.txt
test_07 subtask_01_07.txt
test_08 subtask_01_08.txt
test_09 subtask_01_09.txt
test_10 subtask_01_10.txt
Case Name Status Exec Time Memory
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