【paiza 演習問題】島探し (paizaランク S )（タイムアウト）

10778 ワード
paiza Python3 Python3 テキストリンク

対象

これは paizaランク S 相当の練習問題としてここにあった問題の解答を記録するものであり、初心者向けです。
（上級者の方のアドバイスは頂きたいです……）

概要

入力値ケース９にてタイムアウトを吐かれたのでリファクタリングを行いたい。（未考察、後日追記します）

コード

def out_of_area_check(width, height, x, y):
    x_in_area = 0 <= x < width
    y_in_area = 0 <= y < height
    #print(width, height, x, y)
    #print(x_in_area, y_in_area)
    return x_in_area and y_in_area


def island_seek(frontline_x, frontline_y, value_map, index, width, height):
    while len(frontline_x) > 0:
        #print('check')
        for _i, _j in zip([+1, -1, 0, 0],[0, 0, +1, -1]):
            x = frontline_x[0] + _i
            y = frontline_y[0] + _j
            if out_of_area_check(width, height, x, y):
                #print(x, y)
                if value_map[y][x] == -1:
                    value_map[y][x] = index
                    frontline_y.append(y)
                    frontline_x.append(x)

        del frontline_x[0]
        del frontline_y[0]
    else:
        return


def peninsula_seek(frontline_x, frontline_y, value_map, index, width, height):
    for _x in range(width):
        for _y in range(height):
            if value_map[_y][_x] == -1:
                value_map[_y][_x] = index
                frontline_y.append(_y)
                frontline_x.append(_x)
                return True
    else:
        return False


def solve():
    width, height = map(int, input().split())
    value_map = [list(map(int, input().split())) for _ in range(height)]
    frontline_x = []
    frontline_y = []
    index = 0
    for j in range(width):
        for i in range(height):
            if value_map[i][j] == 1:
                value_map[i][j] = -1

    peninsula = True
    while peninsula:
        index += 1
        #print('index+1')
        peninsula = peninsula_seek(frontline_x, frontline_y, value_map, index, width, height)

        #print(value_map)
        if peninsula:
            island_seek(frontline_x, frontline_y, value_map, index, width, height)
            #print(value_map)
        else:
            print(index-1)
            return


if __name__ == "__main__":
    solve()
Codeforces 1154 - A/B/C/D/E/F/G - (Undone)
JAvaでよく使われる注釈