Implement Depth-First Search (DFS) and Breadth-First Search (BFS) in python

What i did

AtCoder Typical Contest 001 A-I implemented depth-first search in python. Since this problem can be solved by either depth-first search (DFS) or breadth-first search (BFS), we implemented both. Depth-first search was implemented with a pattern using a recursive function and a pattern using a stack (LIFO).

DFS

Cases using recursive functions

#A Depth-first search recursive function
import sys
sys.setrecursionlimit(10**7) #Recursive function call restrictions

def dfs(v_x, v_y, seen_list, c_list):
    if v_x < 0 or v_y < 0 or v_x >= w or v_y >= h:
        return
    if seen_list[v_y][v_x]:
        return
    if c_list[v_y][v_x] == "#":
        return
    seen_list[v_y][v_x] = True
    dfs(v_x+1,v_y,seen_list,c_list)
    dfs(v_x-1,v_y,seen_list,c_list)
    dfs(v_x,v_y+1,seen_list,c_list)
    dfs(v_x,v_y-1,seen_list,c_list)
    
h, w = map(int, input().split())
seen_list = [[False] * w for i in range(h)]
c_list = []
s = []
g = []
for i in range(h):
    _tmp = list(input())
    if "s" in _tmp:
        s = [_tmp.index("s"),i]
    if "g" in _tmp:
        g = [_tmp.index("g"),i]
    c_list.append(_tmp)

dfs(s[0],s[1],seen_list,c_list)

if seen_list[g[1]][g[0]]:
    print("Yes")
else:
    print("No")

Case using stack

#A Depth-first search stack(LIFO)
from collections import deque

def dfs(stack, seen_list, c_list):
    while len(stack)>0:
        v_x, v_y = stack.pop()
        if v_x < 0 or v_y < 0 or v_x >= w or v_y >= h:
            continue
        if seen_list[v_y][v_x]:
            continue
        if c_list[v_y][v_x] == "#":
            continue
        seen_list[v_y][v_x] = True
        stack.append([v_x+1,v_y])
        stack.append([v_x-1,v_y])
        stack.append([v_x,v_y+1])
        stack.append([v_x,v_y-1])
    
h, w = map(int, input().split())
seen_list = [[False] * w for i in range(h)]
c_list = []
s = []
g = []
stack = deque()

for i in range(h):
    _tmp = list(input())
    if "s" in _tmp:
        s = [_tmp.index("s"),i]
    if "g" in _tmp:
        g = [_tmp.index("g"),i]
    c_list.append(_tmp)

stack.append(s)
dfs(stack,seen_list,c_list)

if seen_list[g[1]][g[0]]:
    print("Yes")
else:
    print("No")

BFS

#A Depth-first search Queue to solve with breadth-first search(FIFO)
from collections import deque

def bfs(que, seen_list, c_list):
    while len(que)>0:
        v_x, v_y = que.pop()
        if v_x < 0 or v_y < 0 or v_x >= w or v_y >= h:
            continue
        if seen_list[v_y][v_x]:
            continue
        if c_list[v_y][v_x] == "#":
            continue
        seen_list[v_y][v_x] = True
        que.appendleft([v_x+1,v_y])
        que.appendleft([v_x-1,v_y])
        que.appendleft([v_x,v_y+1])
        que.appendleft([v_x,v_y-1])
    
h, w = map(int, input().split())
seen_list = [[False] * w for i in range(h)]
c_list = []
s = []
g = []
que = deque()

for i in range(h):
    _tmp = list(input())
    if "s" in _tmp:
        s = [_tmp.index("s"),i]
    if "g" in _tmp:
        g = [_tmp.index("g"),i]
    c_list.append(_tmp)

que.append(s)
bfs(que,seen_list,c_list)

if seen_list[g[1]][g[0]]:
    print("Yes")
else:
    print("No")