提出 #7102797


ソースコード 拡げる

Copy
def solve():
    c = read()
    result = think(c)
    write(result)


def read():
    h, w = read_int(2)
    c = []
    for y in range(h):
        buf = read_line(w)
        c.append(list(buf))
    return c


def read_int(n):
    return list(map(int, read_line().split(' ')))[:n]


def read_line(n=0):
    if n == 0:
        return input().rstrip()
    else:
        return input().rstrip()[:n]


def think(c):
    w, h = get_area(c)

    wall = '#'
    start = 's'
    goal = 'g'

    sx, sy = find(c, start)
    gx, gy = find(c, goal)

    visited_area = [[0 for x in range(w)] for y in range(h)]

    search(c, sx, sy, w, h, visited_area)

    if visited_area[gy][gx] == 0:
        return 'No'
    else:
        return 'Yes'


def search(c, x, y, w, h, visited_area):
    if not (0 <= x < w and 0 <= y < h and c[y][x] != '#' and visited_area[y][x] == 0):
        return
    if visited_area[y][x] == 1:
        return
    visited_area[y][x] = 1
    search(c, x + 1, y, w, h, visited_area)
    search(c, x - 1, y, w, h, visited_area)
    search(c, x, y + 1, w, h, visited_area)
    search(c, x, y - 1, w, h, visited_area)


def get_area(c):
    h = len(c)
    w = len(c[0])
    return w, h


def find(c, mark):
    w, h = get_area(c)
    for y in range(h):
        for x in range(w):
            if c[y][x] == mark:
                return x, y


def write(result):
    print(result)


if __name__ == '__main__':
    import sys
    sys.setrecursionlimit(300000)
    solve()

提出情報

提出日時
問題 A - 深さ優先探索
ユーザ vineyoshi
言語 Python (3.4.3)
得点 100
コード長 1552 Byte
結果
実行時間 612 ms
メモリ 149848 KB

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 100 / 100
結果
× 5
× 83
セット名 テストケース
Sample 00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt, 00_sample_04.txt, 00_sample_05.txt
All 00_min_01.txt, 00_min_02.txt, 00_min_03.txt, 00_min_04.txt, 00_min_05.txt, 00_min_06.txt, 00_min_07.txt, 00_min_08.txt, 00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt, 00_sample_04.txt, 00_sample_05.txt, 01_rnd_00.txt, 01_rnd_01.txt, 01_rnd_02.txt, 01_rnd_03.txt, 01_rnd_04.txt, 01_rnd_05.txt, 01_rnd_06.txt, 01_rnd_07.txt, 01_rnd_08.txt, 01_rnd_09.txt, 01_rnd_10.txt, 01_rnd_11.txt, 01_rnd_12.txt, 01_rnd_13.txt, 01_rnd_14.txt, 01_rnd_15.txt, 01_rnd_16.txt, 01_rnd_17.txt, 01_rnd_18.txt, 01_rnd_19.txt, 02_rndhard_00.txt, 02_rndhard_01.txt, 02_rndhard_02.txt, 02_rndhard_03.txt, 02_rndhard_04.txt, 02_rndhard_05.txt, 02_rndhard_06.txt, 02_rndhard_07.txt, 02_rndhard_08.txt, 02_rndhard_09.txt, 02_rndhard_10.txt, 02_rndhard_11.txt, 02_rndhard_12.txt, 02_rndhard_13.txt, 02_rndhard_14.txt, 02_rndhard_15.txt, 02_rndhard_16.txt, 02_rndhard_17.txt, 02_rndhard_18.txt, 02_rndhard_19.txt, 02_rndhard_20.txt, 02_rndhard_21.txt, 02_rndhard_22.txt, 02_rndhard_23.txt, 02_rndhard_24.txt, 02_rndhard_25.txt, 02_rndhard_26.txt, 02_rndhard_27.txt, 02_rndhard_28.txt, 02_rndhard_29.txt, 02_rndhard_30.txt, 02_rndhard_31.txt, 02_rndhard_32.txt, 02_rndhard_33.txt, 02_rndhard_34.txt, 02_rndhard_35.txt, 02_rndhard_36.txt, 02_rndhard_37.txt, 02_rndhard_38.txt, 02_rndhard_39.txt, 03_rndhardsmall_00.txt, 03_rndhardsmall_01.txt, 03_rndhardsmall_02.txt, 03_rndhardsmall_03.txt, 03_rndhardsmall_04.txt, 03_rndhardsmall_05.txt, 03_rndhardsmall_06.txt, 03_rndhardsmall_07.txt, 03_rndhardsmall_08.txt, 03_rndhardsmall_09.txt
ケース名 結果 実行時間 メモリ
00_min_01.txt 18 ms 3192 KB
00_min_02.txt 18 ms 3188 KB
00_min_03.txt 18 ms 3192 KB
00_min_04.txt 17 ms 3192 KB
00_min_05.txt 18 ms 3188 KB
00_min_06.txt 18 ms 3188 KB
00_min_07.txt 18 ms 3188 KB
00_min_08.txt 18 ms 3192 KB
00_sample_01.txt 18 ms 3192 KB
00_sample_02.txt 18 ms 3188 KB
00_sample_03.txt 18 ms 3192 KB
00_sample_04.txt 18 ms 3192 KB
00_sample_05.txt 18 ms 3192 KB
01_rnd_00.txt 57 ms 7540 KB
01_rnd_01.txt 573 ms 133336 KB
01_rnd_02.txt 385 ms 60760 KB
01_rnd_03.txt 597 ms 88044 KB
01_rnd_04.txt 546 ms 125800 KB
01_rnd_05.txt 42 ms 7540 KB
01_rnd_06.txt 353 ms 40548 KB
01_rnd_07.txt 391 ms 67440 KB
01_rnd_08.txt 43 ms 7540 KB
01_rnd_09.txt 60 ms 7540 KB
01_rnd_10.txt 236 ms 15200 KB
01_rnd_11.txt 59 ms 7540 KB
01_rnd_12.txt 502 ms 103920 KB
01_rnd_13.txt 481 ms 100968 KB
01_rnd_14.txt 49 ms 7540 KB
01_rnd_15.txt 301 ms 31064 KB
01_rnd_16.txt 65 ms 7540 KB
01_rnd_17.txt 294 ms 20084 KB
01_rnd_18.txt 50 ms 7540 KB
01_rnd_19.txt 612 ms 149848 KB
02_rndhard_00.txt 58 ms 7540 KB
02_rndhard_01.txt 58 ms 7540 KB
02_rndhard_02.txt 97 ms 9076 KB
02_rndhard_03.txt 92 ms 9076 KB
02_rndhard_04.txt 50 ms 7540 KB
02_rndhard_05.txt 51 ms 7540 KB
02_rndhard_06.txt 47 ms 7540 KB
02_rndhard_07.txt 46 ms 7540 KB
02_rndhard_08.txt 65 ms 7796 KB
02_rndhard_09.txt 65 ms 7796 KB
02_rndhard_10.txt 59 ms 7924 KB
02_rndhard_11.txt 58 ms 7924 KB
02_rndhard_12.txt 54 ms 7796 KB
02_rndhard_13.txt 54 ms 7796 KB
02_rndhard_14.txt 68 ms 8052 KB
02_rndhard_15.txt 67 ms 8052 KB
02_rndhard_16.txt 45 ms 7540 KB
02_rndhard_17.txt 45 ms 7540 KB
02_rndhard_18.txt 44 ms 7540 KB
02_rndhard_19.txt 45 ms 7540 KB
02_rndhard_20.txt 44 ms 7668 KB
02_rndhard_21.txt 45 ms 7668 KB
02_rndhard_22.txt 64 ms 8052 KB
02_rndhard_23.txt 61 ms 8052 KB
02_rndhard_24.txt 54 ms 7540 KB
02_rndhard_25.txt 55 ms 7540 KB
02_rndhard_26.txt 48 ms 7540 KB
02_rndhard_27.txt 46 ms 7540 KB
02_rndhard_28.txt 55 ms 7540 KB
02_rndhard_29.txt 55 ms 7540 KB
02_rndhard_30.txt 48 ms 7540 KB
02_rndhard_31.txt 48 ms 7540 KB
02_rndhard_32.txt 61 ms 7796 KB
02_rndhard_33.txt 62 ms 7796 KB
02_rndhard_34.txt 55 ms 7540 KB
02_rndhard_35.txt 54 ms 7540 KB
02_rndhard_36.txt 48 ms 7540 KB
02_rndhard_37.txt 48 ms 7540 KB
02_rndhard_38.txt 55 ms 7668 KB
02_rndhard_39.txt 55 ms 7668 KB
03_rndhardsmall_00.txt 17 ms 3192 KB
03_rndhardsmall_01.txt 18 ms 3192 KB
03_rndhardsmall_02.txt 17 ms 3188 KB
03_rndhardsmall_03.txt 18 ms 3188 KB
03_rndhardsmall_04.txt 18 ms 3188 KB
03_rndhardsmall_05.txt 18 ms 3188 KB
03_rndhardsmall_06.txt 18 ms 3188 KB
03_rndhardsmall_07.txt 18 ms 3188 KB
03_rndhardsmall_08.txt 18 ms 3188 KB
03_rndhardsmall_09.txt 18 ms 3192 KB