PAST5G

https://gyazo.com/3790c397c786b793094fb8a7167295bd

Consider a graph with a square as a vertex and adjacent squares connected by edges.

The number of vertices is as small as 16 at the highest

DFS "path through all vertices" starting at each vertex of the graph

Theoretical estimate of the computational complexity of this is not available, but it is small, so the decision was made based on the assumption that it would be possible.

When the given square has 1 square, there are zero edges on the graph. This is the corner case with WA.

but this is the problem with not making a list of vertices in the first place.

The set of starting points of an edge must be the set of vertices because the edge is bi-directional" - wrong, there are cases where there is no edge.

The map reads [Putting a guard on when loading a map

Maybe the part about graphing by adjacency could be made into a library.

code:python

def solve(H, W, data):

from collections import defaultdict

# make graph

edges = defaultdict(list)

count = 0

a_vertex = None

for x in range(H):

for y in range(W):

v = W * x + y

pos = WIDTH + 1 + WIDTH * x + y

a_vertex = v

count += 1

if count == 1: # (1)

print(1)

v = a_vertex

x, y = divmod(v, W)

print(x + 1, y + 1)

for start in edges:

path = []

def visit(cur):

path.append(cur)

if len(path) == count:

return True

r = visit(next)

if r:

return True

path.pop()

if visit(start):

print(count)

for v in path:

x, y = divmod(v, W)

print(x + 1, y + 1)

return

---