Submission #668527

---

Source Code Expand

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

import itertools
import numpy
import sys

DS = [(1, 0), (-1, 0), (0, 1), (0, -1)]
H = 30
W = 30
TRIAL = 20
INF = 100000


class Solver(object):

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

    def initialize(self):
        self.stage = self.original_stage.copy()
        self.hands = []
        self.naive_counter = 0

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

    def shuffle_indices(self):
        numpy.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.naive_counter += 1
                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.initialize()
        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)
    min_naive_counter = INF
    optimal_hands = None
    for _ in range(TRIAL):
        solver.use_multiple_adj_solution()
        new_naive_counter = solver.naive_counter
        if new_naive_counter < min_naive_counter:
            min_naive_counter = new_naive_counter
            optimal_hands = solver.hands
    for r, c in optimal_hands:
        print("{} {}".format(r, c))


if __name__ == '__main__':
    main()

Submission Info

Judge Result