Submission #667813

---

Source Code Expand

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

import itertools
import numpy
import random
import sys

DS = [(1, 0), (-1, 0), (0, 1), (0, -1)]
H = 30
W = 30


class Solver(object):

    def __init__(self, stage, deltas=DS):
        self.stage = stage
        self.hands = None
        self.deltas = deltas[:]
        self.indices = numpy.array(list(itertools.product(range(H), range(W))))
        self.init_hands()

    def init_hands(self):
        self.hands = []

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

    def shuffle_indices(self):
        random.shuffle(self.indices)

    def naive_solution(self):
        for r, c in itertools.product(range(H), range(W)):
            cell = self.stage[r, c]
            if cell <= 0:
                continue
            for _ in range(cell):
                self.decrement(r, c)

    def search_adj(self, r0, c0):
        for dr, dc in self.deltas:
            (r, c) = (r0 + dr, c0 + dc)
            if r < 0 or r >= H or c < 0 or c >= W:
                continue
            elif 0 < self.stage[r, c] == self.stage[r0, c0]:
                self.decrement(r, c)
                self.search_adj(r, c)
                break

    def use_multiple_adj_solution(self):
        self.shuffle_indices()
        for r0, c0 in self.indices:
            if self.stage[r0, c0] <= 0:
                continue
            self.decrement(r0, c0)
            self.search_adj(r0, c0)
        self.naive_solution()


def main():
    sys.setrecursionlimit(10000)
    stage = numpy.array([list(map(int, input().split())) for _ in range(H)])
    solver = Solver(stage)
    solver.use_multiple_adj_solution()
    for r, c in solver.hands:
        print("{} {}".format(r, c))
    # print(solver.stage)


if __name__ == '__main__':
    main()

Submission Info

Judge Result