Submission #420574

---

Source Code Expand

def dfs(M, p):                                                                      
    visited, stack = set(), [p]                                                     
    while stack:                                                                    
        vertex = stack.pop(0)                                                       
        if vertex[0] < 0 or vertex[0] >= len(M) or vertex[1] < 0 or vertex[1] >= len(M[0]):                                                                             
            continue                                                                
        if M[vertex[0]][vertex[1]] == "g":                                          
            return True                                                             
        if vertex not in visited:                                                   
            visited.add(vertex)                                                     
            for i in [-1, 0, 1]:                                                    
                for j in [-1, 0, 1]:                                                
                    stack.append((vertex[0]+i, vertex[1]+j,))                       
    return False                                                                    
                                                                                    
if __name__ == "__main__":                                                          
    H, W = [int(i) for i in input().strip().split()]                                
    M = []                                                                          
    for i in range(H):                                                              
        tmp = [s for s in list(input())]                                            
        if "s" in tmp:                                                              
            ps = (i, tmp.index("s"),)                                               
        M.append(tmp)                                                               
    if dfs(M, ps):                                                                  
        print("Yes")                                                                
    else:                                                                           
        print("No")  

Submission Info

Judge Result