PAST5H

https://gyazo.com/f0e4b1e3e154ed74f38484fa80a6fd5a

Initial Considerations

Determine if it can be moved

Construct a graph and DFS "can you reach the goal" from each starting point

10^6 vertices, okay?

Many starts, one goal.

The graph is made with inverted edges, and the search is made for reachable vertices with the goal as the starting point.

Each vertex has only 4 edges at most, so O(N) will do.

Consideration complete

mounting

Create a graph with inverse edges and mark the vertices to be reached by the recursive call DFS from the goal.

Explore using map data without constructing a graph

In Python3, 1MLE

Rewrite search in recursive calls to a while loop

1TLE

Reduce string concatenation in result output

Append strings to a list without joining them in a loop and join them at the end

AC

consideration

This time, the problem conditions lead to a worst case vertex count of 10^6

In the case of a Python implementation with a per-vertex list, the construction cost itself is not negligible

What's wrong with MLEs...

Not reducing string concatenation is simply inadvertent.

I submitted a graph that I tried to reduce only the string concatenation while building the graph just to be sure, but this was 9 TLE, so it's not the main factor.

code:python

def solve(H, W, R, C, world):

stack = {WIDTH * R + C}

while len(stack) > 0:

pos = stack.pop()

next = pos - 1

stack.add(next)

next = pos + 1

stack.add(next)

next = pos + WIDTH

stack.add(next)

next = pos - WIDTH

stack.add(next)

for y in range(ORIGINAL_HEIGHT):

line = []

for x in range(ORIGINAL_WIDTH):

pos = WIDTH + 1 + WIDTH * y + x

line.append("#")

line.append("o")

else:

line.append("x")

print("".join(line))

---