Submission #7102724

---

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

Judge Result