結果

問題 No.460 裏表ちわーわ
ユーザー sue_charosue_charo
提出日時 2017-06-04 02:27:56
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
TLE  
実行時間 -
コード長 2,325 bytes
コンパイル時間 114 ms
コンパイル使用メモリ 12,928 KB
実行使用メモリ 35,328 KB
最終ジャッジ日時 2024-09-22 04:40:52
合計ジャッジ時間 3,813 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 43 ms
18,844 KB
testcase_01 TLE -
testcase_02 -- -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

# coding: utf-8
import array, bisect, collections, copy, heapq, itertools, math, random, re, string, sys, time
sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
MOD = 10 ** 9 + 7


def II(): return int(input())
def ILI(): return list(map(int, input().split()))
def IAI(LINE): return [ILI() for __ in range(LINE)]
def IDI(): return {key: value for key, value in ILI()}


def read():
    M, N = ILI()
    # a[row][col]
    a = IAI(N)
    return (M, N, a)


def change_board(board, x, y, M, N):
    if N == 1:
        l_x = [0]
    elif N == 2:
        l_x = [0, 1]
    else:
        if x == 0:
            l_x = [0, 1]
        elif x == N - 1:
            l_x = [N - 2, N - 1]
        else:
            l_x = [x - 1, x, x + 1]

    if M == 1:
        l_y = [0]
    elif M == 2:
        l_y = [0, 1]
    else:
        if y == 0:
            l_y = [0, 1]
        elif y == M - 1:
            l_y = [M - 2, M - 1]
        else:
            l_y = [y - 1, y, y + 1]

    ret_board = copy.deepcopy(board)
    for in_x in l_x:
        for in_y in l_y:
            ret_board[in_y][in_x] = (ret_board[in_y][in_x] + 1) % 2

    return ret_board


def bool_board(board):
    for row in board:
        if sum(row) != 0:
            return False
    return True


def board_to_tuple(board):
    l_ret = []
    for row in board:
        l_ret += row
    t_ret = tuple(l_ret)
    return t_ret


def solve(M, N, a):
    set_check = set()
    if bool_board(a):
        return 0
    else:
        ans = 0
        stack = [a]
        set_check.add(board_to_tuple(a))
    while len(stack) != 0:
        next_stack = []
        ans += 1
        for b in stack:
            for x in range(N):
                for y in range(M):
                    ret_board = change_board(b, x, y, M, N)
                    if bool_board(ret_board):
                        return ans
                    else:
                        tup_board = board_to_tuple(ret_board)
                        if tup_board in set_check:
                            continue
                        else:
                            set_check.add(tup_board)
                            next_stack.append(ret_board)

        stack = copy.deepcopy(next_stack)

    return "impossible"


def main():
    params = read()
    print(solve(*params))


if __name__ == "__main__":
    main()
0