AOJ 1160 島はいくつある？とABC 007 C 幅優先探索

qiita.com

DFSとBFSの問題。 愚直な実装でいける。

import sys

sys.setrecursionlimit(1000000)


def rec(y, x, f):
    f[y][x] = '0'
    for dy, dx in [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0),
            (1, 1)]:
        if 0 <= y+dy < len(f) and 0 <= x+dx < len(f[0]) and f[y+dy][x+dx] == '1':
            rec(y+dy, x+dx, f)


def main():
    while True:
        w, h = [int(i) for i in input().split()]
        if w == 0 and h == 0:
            break
        field = []
        for i in range(h):
            field.append(input().split())
        ans = 0
        for i in range(h):
            for j in range(w):
                if field[i][j] == '1':
                    rec(i, j, field)
                    ans += 1
        print(ans)
    print(0)


if __name__ == '__main__':
    main()

と

from collections import deque
BIG = 100000


def main():
    h, w = [int(i) for i in input().split()]
    sy,sx = [int(i)-1 for i in input().split()]
    gy,gx = [int(i)-1 for i in input().split()]
    field = []
    d = [[BIG for i in range(w)] for j in range(h)]
    for i in range(h):
        field.append(list(input()))
    q = deque()
    q.appendleft([sy, sx])
    d[sy][sx] = 0
    ans = 100000
    while q:
        y, x = q.pop()
        if y == gy and x == gx:
            break
        field[y][x] = '#'
        for dy, dx in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            if 0 <= y+dy < h and 0 <= x+dx < w and field[y+dy][x+dx] == '.' \
                and d[y+dy][x+dx] == BIG:
                q.appendleft([y+dy, x+dx])
                d[y+dy][x+dx] = d[y][x]+1
    print(d[gy][gx])


if __name__ == '__main__':
    main()

BFSは、既に訪れたところを訪れないようにしないと、時間がかかってTLEになるので、別フィールドを用意して、訪れたか判定するのが良い。