For all subtasks, we can represent the game as a graph where each board configuration is a vertex. An ~N \times M~ board will have ~\frac{(N \cdot M)!}{2}~ valid configurations. There are a number of ways to do this, such as indexing permutations, bitmask techniques, or strings.

Subtask 1

For the first subtask, there are only ~12~ possible board configurations. We can randomly make ~12~ moves for each player and keep track of the minimum moves for each player to reach the target board. If we do this enough times, we will have the correct answer with high probability.

Time Complexity: depends on implementation

Subtask 2

For the second subtask, we can perform a breadth first search from each player's starting board, for each game, and select the player with the least number of moves.

Time Complexity: ~\mathcal{O}((N \times M)! \times K \times Q)~

Subtask 3

For the third subtask, a key observation is that the starting board configuration does not change for each player. We can perform a single breadth first search from each player's starting board, creating a distance array. To determine the answer, we will check the distance array for each player and select the minimum.

Time Complexity: ~\mathcal{O}(K \times ((N \times M)! + Q \times N \times M))~

Subtask 4

For the fourth subtask, we can perform a multi-source breadth first search from each of the players instead of a single-source breadth first search. We will keep track of the distance and player for each vertex. The answer can then be determined in ~\mathcal{O}(1)~ time for each game. This solution should work for subtasks 1 to 3 as well.

Time Complexity: ~\mathcal{O}((N \times M)! + (K + Q) \times N \times M)~

Subtask 5

For the last subtask, there is only a single game, but a very large graph. A few key observations are that the graph is fairly random and that since the starting and target boards are generated uniformly at random, we do not have to worry about the worst cases. Thus, we can perform a tridirectional breadth first search from the two starting board and ending board configurations. When a path starting from the target board intersects any of paths from the player's boards, we know we have found the minimum answer (in theory, we will have to keep checking all vertices at that depth to find the minimum player index, but with random data, it is very unlikely that the two players will have the same number of moves). By the birthday paradox, this will result in visiting approximately ~\sqrt{(N \times M)!}~ vertices (in practice, it is slightly more than that). Note that this solution will not pass subtask 4.

Time Complexity: ~\mathcal{O}((K + Q) \times \sqrt{(N \times M)!})~