Daily AtCoder # 26 in Python

Introduction

#25 Today, I will solve the Introduction problem of DFS. I referred to this article.

DFS stands for Depth-First Search. A similar name is breadth-first search (BFS). As the name suggests, DFS feels like going from the point on the current graph to the point where you can go. Detailed explanation

The problem this time is that it doesn't specify where s is. So, first, look for the location of's'. When you find the's', add the coordinates of s to the stack (type is collections.deque, not list). The stack retrieves the last element you put in first. Next, set the coordinate of s in visited_list to 1. The meaning of 1 is 0 or 1 to judge whether it has been searched. This visited_list is a set of searched points. Here is the contents of dfs.

While until the stack is empty.
Pop out the new h, w (current location) from the stack
If h, w is'g', return'Yes' and exit.
If h and w are not'g', proceed in each direction. This problem is in the [1, 0], [-1, 0], [0, 1], [0, -1] directions.
Represents the coordinates of the current location + the destination in each direction.
I don't think if the destination is out of the question, so continue.
If the destination is not'#' and has not been searched, set visited_list [coordinates] to 1 and add new coordinates to the stack.

from collections import deque

h_in, w_in = map(int,input().split())
c = [input() for _ in range(h_in)]

for n1,c_w in enumerate(c):
    for n2,c1 in enumerate(c_w):
        if c1 == "s":
            s_h = n1
            s_w = n2

stack = deque([[s_h,s_w]])

visited_list = [[0]*w_in for _ in range(h_in)]
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_in or new_w < 0 or new_w >= w_in:
                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))

Summary

I passed through when the problem of the graph came out, but I want to study hard and be able to solve it. I will do my best because it will not take root with just one question. see you. good night