結果

問題 No.460 裏表ちわーわ
ユーザー sue_charo
提出日時 2017-06-04 02:27:56
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
TLE  
実行時間 -
コード長 2,325 bytes
コンパイル時間 114 ms
コンパイル使用メモリ 12,928 KB
実行使用メモリ 35,328 KB
最終ジャッジ日時 2024-09-22 04:40:52
合計ジャッジ時間 3,813 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 1 TLE * 1 -- * 26
権限があれば一括ダウンロードができます

ソースコード

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