Submission #7102857


Source Code Expand

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)]
 
    stack = []
    push([sx, sy], stack)
 
    while stack:
        x, y = pop(stack)
        if visited_area[y][x] == 0:
            visited_area[y][x] = 1
            if can_go_to(c, x + 1, y):
                push([x + 1, y], stack)
            if can_go_to(c, x - 1, y):
                push([x - 1, y], stack)
            if can_go_to(c, x, y + 1):
                push([x, y + 1], stack)
            if can_go_to(c, x, y - 1):
                push([x, y - 1], stack)
        else:
            continue
 
    if visited_area[gy][gx] == 0:
        return 'No'
    else:
        return 'Yes'
 
 
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 push(what, stack):
    stack.insert(0, what)
 
 
def pop(stack):
    return stack.pop(0)
 
 
def can_go_to(c, x, y):
    w, h = get_area(c)
    return 0 <= x < w and 0 <= y < h and c[y][x] != '#'
 
 
def write(result):
    print(result)
 
 
if __name__ == '__main__':
    solve()

Submission Info

Submission Time
Task A - 深さ優先探索
User vineyoshi
Language Python (3.4.3)
Score 0
Code Size 1814 Byte
Status TLE
Exec Time 2104 ms
Memory 12340 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 100
Status
AC × 5
AC × 72
TLE × 11
Set Name Test Cases
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
Case Name Status Exec Time Memory
00_min_01.txt AC 18 ms 3192 KB
00_min_02.txt AC 18 ms 3192 KB
00_min_03.txt AC 18 ms 3192 KB
00_min_04.txt AC 18 ms 3192 KB
00_min_05.txt AC 18 ms 3192 KB
00_min_06.txt AC 18 ms 3192 KB
00_min_07.txt AC 18 ms 3192 KB
00_min_08.txt AC 18 ms 3192 KB
00_sample_01.txt AC 18 ms 3192 KB
00_sample_02.txt AC 18 ms 3192 KB
00_sample_03.txt AC 18 ms 3192 KB
00_sample_04.txt AC 18 ms 3192 KB
00_sample_05.txt AC 18 ms 3192 KB
01_rnd_00.txt AC 58 ms 7540 KB
01_rnd_01.txt TLE 2104 ms 12224 KB
01_rnd_02.txt TLE 2104 ms 11744 KB
01_rnd_03.txt TLE 2104 ms 12340 KB
01_rnd_04.txt TLE 2104 ms 12020 KB
01_rnd_05.txt AC 43 ms 7540 KB
01_rnd_06.txt TLE 2104 ms 10684 KB
01_rnd_07.txt TLE 2104 ms 11048 KB
01_rnd_08.txt AC 43 ms 7540 KB
01_rnd_09.txt AC 60 ms 7540 KB
01_rnd_10.txt AC 1978 ms 8860 KB
01_rnd_11.txt AC 59 ms 7540 KB
01_rnd_12.txt TLE 2104 ms 11816 KB
01_rnd_13.txt TLE 2104 ms 11748 KB
01_rnd_14.txt AC 49 ms 7540 KB
01_rnd_15.txt TLE 2104 ms 9948 KB
01_rnd_16.txt AC 64 ms 7540 KB
01_rnd_17.txt TLE 2104 ms 9720 KB
01_rnd_18.txt AC 49 ms 7540 KB
01_rnd_19.txt TLE 2104 ms 12316 KB
02_rndhard_00.txt AC 62 ms 7540 KB
02_rndhard_01.txt AC 62 ms 7540 KB
02_rndhard_02.txt AC 227 ms 7668 KB
02_rndhard_03.txt AC 205 ms 7668 KB
02_rndhard_04.txt AC 50 ms 7540 KB
02_rndhard_05.txt AC 50 ms 7540 KB
02_rndhard_06.txt AC 48 ms 7540 KB
02_rndhard_07.txt AC 46 ms 7540 KB
02_rndhard_08.txt AC 84 ms 7540 KB
02_rndhard_09.txt AC 85 ms 7540 KB
02_rndhard_10.txt AC 78 ms 7540 KB
02_rndhard_11.txt AC 79 ms 7540 KB
02_rndhard_12.txt AC 63 ms 7540 KB
02_rndhard_13.txt AC 63 ms 7540 KB
02_rndhard_14.txt AC 89 ms 7540 KB
02_rndhard_15.txt AC 87 ms 7540 KB
02_rndhard_16.txt AC 47 ms 7540 KB
02_rndhard_17.txt AC 47 ms 7540 KB
02_rndhard_18.txt AC 47 ms 7540 KB
02_rndhard_19.txt AC 46 ms 7540 KB
02_rndhard_20.txt AC 51 ms 7540 KB
02_rndhard_21.txt AC 52 ms 7540 KB
02_rndhard_22.txt AC 78 ms 7540 KB
02_rndhard_23.txt AC 70 ms 7540 KB
02_rndhard_24.txt AC 58 ms 7540 KB
02_rndhard_25.txt AC 56 ms 7540 KB
02_rndhard_26.txt AC 51 ms 7540 KB
02_rndhard_27.txt AC 48 ms 7540 KB
02_rndhard_28.txt AC 58 ms 7540 KB
02_rndhard_29.txt AC 59 ms 7540 KB
02_rndhard_30.txt AC 49 ms 7540 KB
02_rndhard_31.txt AC 48 ms 7540 KB
02_rndhard_32.txt AC 74 ms 7540 KB
02_rndhard_33.txt AC 73 ms 7540 KB
02_rndhard_34.txt AC 57 ms 7540 KB
02_rndhard_35.txt AC 57 ms 7540 KB
02_rndhard_36.txt AC 50 ms 7540 KB
02_rndhard_37.txt AC 49 ms 7540 KB
02_rndhard_38.txt AC 62 ms 7540 KB
02_rndhard_39.txt AC 62 ms 7540 KB
03_rndhardsmall_00.txt AC 18 ms 3192 KB
03_rndhardsmall_01.txt AC 18 ms 3192 KB
03_rndhardsmall_02.txt AC 18 ms 3192 KB
03_rndhardsmall_03.txt AC 18 ms 3192 KB
03_rndhardsmall_04.txt AC 18 ms 3192 KB
03_rndhardsmall_05.txt AC 18 ms 3192 KB
03_rndhardsmall_06.txt AC 18 ms 3192 KB
03_rndhardsmall_07.txt AC 18 ms 3192 KB
03_rndhardsmall_08.txt AC 18 ms 3192 KB
03_rndhardsmall_09.txt AC 18 ms 3192 KB