Home>

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]
Input is given from standard input in the following format:

H W
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.

[Output]
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.

Code
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")
Execution results

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