I've described the depth-first search algorithm using recursion, but it seems that a stack overflow has occurred due to a run-time error in some of the sample data at the proconsite. The Please tell us about the problems and how to solve them.Problem
Atcoder Typical Contest 001 A
Takahashi-kun's town is rectangular in shape and is divided into grids. Each side of the rectangle is parallel to east-west and north-south. Each block is either a road or a fence, and Takahashi can move east, west, south, and north, but not diagonally. In addition, the fence compartment cannot pass.
Please judge whether Takahashi can get to the fish shop through the road without breaking the spear.
Input is given from standard input in the following format:
c0,0 c0,1 c0, W−1
c1,0 c1,1 c1, W-1
cH−1,0 cH−1,1 cH−1, W−1
The first line is given as an integer H (1 ≤ H ≤ 500) as the north-south length of the city and an integer W (1 ≤ W ≤ 500) as the east-west length, separated by a space.
The state ci, j (0 ≦ i ≦ H−1,0 ≦ j ≦ W−1) in each section of the grid city is given to the H rows from the second row.
The character ci, j in the i-th line and the j-th character is given as one of s, g,., #, respectively, and the coordinates (j, i) indicate the following state.
"s": Indicates that the parcel is a house.
"g": Indicates that the parcel is a fish shop.
".": Indicates that the section is a road.
"#": Indicates that the section is a fence.
Mr. Takahashi can pass through the house, fish shop and road, but cannot pass through the sea bream.
You can't go outside the given city.
One s and one g are given.
If i can get from the house to the fish shop without breaking the salmon once, output Yes to the standard output on one line if you can't reach it.
import sys h, w = list (map (int, input (). split ())) M = [list (input ()) for _ in range (h)] for i, j in enumerate (M): if "s" in j: sr, sc = i, j.index ("s") def dfs (r, c): M [r] [c] = "#" for i, j in ([-1,0], [1,0], [0, -1], [0,1]): if not (0<= r + i<h and 0<= c + j<w): continue if M [r + i] [c + j] == "g": print ("Yes") sys.exit () if M [r + i] [c + j] == ".": dfs (r + i, c + j) dfs (sr, sc) print ("No")
Code test Submission # 3124726
Answer # 1
Strictly speaking, it is not a stack overflow.
python limits the depth of recursion. The default is 1000.
The upper limit can be changed with the following code.
import sys sys.setrecursionlimit (appropriate number)
During this time, I was answering the same question ...
Python 3.x-Depth-first search problem results in RE (139765) ｜ StackOverflow
- c ++ - stack overflow in a dynamic multidimensional array
- c ++: about stack overflow
- python - i want to stack part of the pandas multiindex column with the original column name
- python - i want to stack after deleting columns in multiindex columns of pandas
- python - how to avoid errors when using ctypes pointers
- python - i want to use the stack to reverse the strings, but an error occurs, so please give me a solution
- python - i want to avoid "no response" when pressing gui button in pyqt
- python 3x - typeerror: 'method' object is not subscriptable
- python - you may need to restart the kernel to use updated packages error
- xcode - pod install [!] no `podfile 'found in the project directory
- vuejs - [vuetify] unable to locate target [data-app] i want to unit test to avoid warning
- android studio - emulator: dsound: could not initialize about the error message directsoundcapture
- android studio - unresolved reference comes out in kotlin
- mysql startup failed [error] innodb: the innodb_system data file 'ibdata1' must be writable
- django - oserror: [winerror 123] the file name, directory name, or volume label syntax is incorrect : '<frozen importlib_boot
- python - importerror: cannot import name md5 error cannot be resolved