競プロ強くなりたいので、このサイト(AtCoder 版！蟻本 (初級編))を参考に、AtCoderの問題を解いてアルゴリズムの基礎固めしています。今回解くのは、AtCoderのA-深さ優先探索。全探索の一種である深さ優先探索(DFS)の典型的な問題です。

問題

東西南北の長方形の街にて、途中の塀を通らず、道を通って、家から魚屋へたどり着けるかという問題です。
※ちなみにこの問題を幅優先探索(BFS)で解くと、辺の重みなしの最短経路問題になります。

解法

今回は再帰を使わず、スタックしていく方法で解きます。Wikipediaの深さ優先探索のページがアルゴリズムの概要がわかりやすいです。

解くポイントとしては、

■DFS一般的な部分

スタックを作成し、未訪問のノードを入れていく
訪問したノードには、訪問済みの印をつける
　※閉路がある場合に必要
スタックから一つずつ取り出し、処理を行う
　※スタックなので「後入れ、先出し」。これがDFSを実現している。

■この問題特有の部分

スタートの位置がわからないので、初めに調べる（＝スタックに入れておく）
親ノード(x, y)に接続しているノードは、(x-1, y), (x+1, y), (x, y-1), (x, y+1)の4通り

といったところでしょうか。
以下、pythonのコードです。

from collections import deque
 
H,W = map(int, input().split())
C = [input() for _ in range(H)]
 
# sの位置をあらかじめ調べておく
for n1,c_w in enumerate(C):
    for n2,c in enumerate(c_w):
        if c == "s":
            s_h = n1
            s_w = n2
            
stack = deque([[s_h, s_w]])  # スタートの位置だけ入ったスタックを作成
 
visited_list = [[0]*W for _ in range(H)]
visited_list[s_h][s_w] = 1
 
def dfs(town, visited_list, stack):
    while len(stack) > 0:
        h, w = stack.pop()
        if town[h][w] == "g":
            return "Yes"
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_h, new_w = h+j, w+k
            if new_h < 0 or new_h >= H or new_w < 0 or new_w >= W:
                continue
            if town[new_h][new_w] != "#" and visited_list[new_h][new_w] == 0:
                visited_list[new_h][new_w] = 1
                stack.append([new_h, new_w])
    
    return "No"
 
print(dfs(C, visited_list, stack))