[Python] DFS (Depth-first Search) ATC001A

ATC001A

It is effective to regard the maze as a graph search.

Sample code


#In python, it gets stuck in the default recursive processing limit, so change it
import sys
sys.setrecursionlimit(1000000)

#Definition of recursive function DFS
def dfs(x, y):
    #mark
    d[x][y] = 1

    #Loop in 4 directions
    for i in range(4):
        X = x + dx[i]
        X = y + dy[i]

        #Determine if X and Y are within the city, have never been, or are not a fence
        if 0 <= X and X < n and 0 <= Y and Y < m and d[X][Y] == 0 and c[X][Y] != "#":
                dfs(X, Y)

#input
n, m = map(int, input().split())
c = [list(input()) for i in range(n)]

#Whether it has been reached (0 is not reached, 1 is reached)
d = [[0] * m for i in range(n)]

#4 directions to move
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

#Start dfs from the starting point
for i in range(n):
    for j in range(m):
        if c[i][j] == "s":
            dfs(i, j)

#Whether you have reached the goal point
for i in range(n):
    for j in range(m):
        if c[i][j] == "g" and d[i][j]:
            print("Yes")
            exit()
print("No")

Recommended Posts

[Python] DFS (Depth-first Search) ATC001A
[Python] DFS (Depth-first Search) ABC157D
Algorithm in Python (depth-first search, dfs)
[Python] Depth-first search and breadth-first search
Implement Depth-First Search (DFS) and Breadth-First Search (BFS) in python
Write a depth-first search in Python
Depth-first search using stack in Python
[Python] DFS AGC044A
I tried to solve AtCoder's depth-first search (DFS) in Python (result: TLE ...)
Sequential search with Python
[Python] Search (itertools) ABC167C
Binary search in Python
[Python] Search (NumPy) ABC165C
Binary search (python2.7) memo
[Python] Binary search ABC155D
python bit full search
Linear search in Python
Binary search with python
Binary search with Python3
Search Twitter using Python
Binary search in Python (binary search)
[Python] BFS (breadth-first search) ABC168D
Search for strings in Python
Search algorithm using word2vec [python]
Homebrew Python --Youtube Search Program
[At Coder] Solve a typical problem of depth-first search (DFS)
Binary search in Python / C ++
Algorithm in Python (binary search)
Full bit search with Python
Search engine work with python
Search twitter tweets with python
[Python] BFS (breadth-first search) ABC007C
Streamline web search with python
Depth-first search (non-recursive type) and lower limit pruning method (Python edition)
[Python algorithm] A program that outputs Sudoku answers from a depth-first search
Algorithm in Python (breadth-first search, bfs)
Learn search with Python # 2bit search, permutation search
Breadth-first search (BPF) Maybe understood (python)
Master linear search! ~ Python implementation version ~
Reproduce One-Touch Search on Python 3.7.3. (Windows 10)
Python 2-minute search and its derivation