Submission #669900

---

Source Code Expand

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import array
import collections
import itertools
import sys

DELTAS = [(1, 0), (-1, 0), (0, 1), (0, -1)]
INF = 100000
INVALID = (-1, -1)
WHITE = 0
GRAY = 1
BLACK = 2


class Solver(object):

    def __init__(self, stage, size, deltas=DELTAS):
        self.stage = stage[:]
        self.size = size
        self.deltas = deltas[:]
        self.hands = None
        self.naive_counter = 0
        self.pred = None
        self.to = None
        self.visited = None
        self.decremented = None
        self.start = (0, 0)
        self.in_queue = None
        self.queues = None
        self.initialize_hands()

    def initialize_hands(self):
        self.hands = []
        self.naive_counter = 0
        self.decremented = collections.defaultdict(bool)

    def initialize_dfs(self):
        self.pred = collections.defaultdict(lambda: INVALID)
        self.to = collections.defaultdict(lambda: INVALID)
        self.visited = collections.defaultdict(lambda: WHITE)
        self.in_queue = collections.defaultdict(bool)
        self.queues = []

    def decrement(self, r, c):
        if self.stage[r][c] > 0:
            self.hands.append((r + 1, c + 1))
            self.stage[r][c] -= 1

    def naive_solution(self):
        for r, c in itertools.product(range(self.size), repeat=2):
            cell = self.stage[r][c]
            if cell > 0:
                for _ in range(cell):
                    self.naive_counter += 1
                    self.decrement(r, c)

    def is_valid_rc(self, r, c):
        return not (r < 0 or r >= self.size or c < 0 or c >= self.size)

    def start_dfs_from(self, r0, c0):
        self.visited[(r0, c0)] = GRAY
        if not self.is_valid_rc(r0, c0):
            return
        cell0 = self.stage[r0][c0]
        if cell0 <= 1:
            return
        for dr, dc in self.deltas:
            (r, c) = (r0 + dr, c0 + dc)
            if not self.is_valid_rc(r, c):
                continue
            if self.visited[(r, c)]:
                continue
            cell = self.stage[r][c]
            if cell0 - cell != 1:
                continue
            self.pred[(r, c)] = (r0, c0)
            self.to[(r0, c0)] = (r, c)
            self.start_dfs_from(r, c)
        self.visited[(r0, c0)] = BLACK

    def perform_dfs(self):
        self.initialize_dfs()
        for r, c in itertools.product(range(self.size), repeat=2):
            if not self.visited[(r, c)]:
                self.start_dfs_from(r, c)

    def construct_forest(self):
        self.perform_dfs()
        keys = list(self.to.keys())
        for r0, c0 in keys:
            if self.in_queue[(r0, c0)]:
                continue
            q = collections.deque()
            q.append((r0, c0))
            r, c = r0, c0
            while True:
                r_next, c_next = self.to[(r, c)]
                if (r_next, c_next) == INVALID:
                    break
                q.append((r_next, c_next))
                self.in_queue[(r_next, c_next)] = True
                r, c = r_next, c_next
            r, c = r0, c0
            while True:
                r_prev, c_prev = self.pred[(r, c)]
                if (r_prev, c_prev) == INVALID:
                    break
                q.appendleft((r_prev, c_prev))
                self.in_queue[(r_prev, c_prev)] = True
                r, c = r_prev, c_prev
            self.queues.append(q)

    def use_dfs_solution(self):
        for _ in range(100):
            self.construct_forest()
            for q in self.queues:
                while q:
                    (r0, c0) = q.popleft()
                    self.decrement(r0, c0)
        self.naive_solution()

    def search_next(self, r0, c0):
        if (r0, c0) == INVALID:
            return
        if self.decremented[(r0, c0)]:
            return
        self.decrement(r0, c0)
        self.decremented[(r0, c0)] = True
        self.search_next(*self.to[(r0, c0)])



def main():
    sys.setrecursionlimit(INF)
    stage = []
    for line in sys.stdin:
        stage.append(array.array("B", map(int, line.split())))
    size = len(stage)
    solver = Solver(stage, size)
    solver.use_dfs_solution()
    for r, c in solver.hands:
        print("{} {}".format(r, c))


if __name__ == '__main__':
    main()

Submission Info

Judge Result