Natjecanje

Dino has been practicing for a package delivery competition for weeks. In the
competition, the winner is the contestant who delivers all the packages from the
warehouse to the designated destinations the fastest. Unfortunately, Dino has only
two hands, so he can carry at most two packages at a time.
He can drop and pick up packages however he wants, as long as he carries at most
two at a time. He can also carry and deliver them in any order, and each package
can be delivered to any destination. After completing his delivery route, there
must be a package at each of the \(k\) destinations.
During the competition, Dino moves on a grid of \(n\) rows and \(m\) columns, where
free cells are marked with ".", obstacles with "#", Dino’s starting cell and all packages with "S", and
package destinations with "X". In one second, he can move to any adjacent cell in the four directions (up,
down, left, or right) that is not an obstacle. Dropping and picking up packages takes negligible time.
Help Dino determine the minimum number of seconds he needs to deliver all packages to their destinations
and return to the starting cell, or print -1 if it is impossible.

In the first line, there are three natural numbers \(n\), \(m\), and \(k\) (\(1 \le n\), \(m \le 500\), \(1 \le k \le 67\)), the number of
rows and columns of the matrix and the number of package destinations.
In each of the next \(n\) lines, there are \(m\) characters \(c_{ij}\) describing the board. Each character of the matrix
will be one of ".", "#", "S", or "X" (without quotes).
The letter "X" will appear exactly \(k\) times in the matrix.

In the first line, print a single number - the minimum number of seconds required for Dino to deliver all
the packages to their destinations and return to the starting cell, \(or -1\) if this is impossible.

생성자가 기록되지 않았습니다.

출처 COCI 2025/2026 Contest 2