Solution by Gabriel-Robert Inelus

In order to solve the problem we must imagine that we are in the middle of an infinite grid at coordinates (0, 0). Hence, at any step we can move from the current position (i, j) to:

• (i+1, j)
• (i-1, j)
• (i, j+1)
• (i, j-1)

as long as we don't pass twice through a position which has been visited before in the current path.

Thus, we will use a backtracking algorithm which generates all these solutions; however, there will be repetitions which must be taken care of.

The actual problem is to find a method to determine whether or not two paths have the same "shape" given that we are allowed to apply some translation operations to them.

The key idea is that we can find an extreme point on the border of the shapes. A good choice can be to find the element (x, y) of a path, which has the smallest x coordinate and, in case of equality, the smallest y coordinate. Then, we normalize the shape by translating it (originally centered at (x, y)) to (0, 0) by subtracting (x, y) (by components) from all the elements of the current path. After this, we will be left with a normalized path which can be stored in a hash map (for instance, we can use STL map to store some vectors, or unordered_map to store some strings).

The result is the size of the hash map.