I found a problem, but I think my solution is too slow. Please give me some advice or tutorials. QwQ
Here's the description of the problem：
You have a $$$3 \times 3$$$ grid, each cell containing a letter. You can swap two adjacent letters (up, down, left, or right). The question is, how many swaps are needed so that no two identical letters are adjacent in the grid? If it is impossible to achieve, return $$$-1$$$. A test case may contain multiple grid.
Sample input:
[["abc", "def", "ghi"], ["aaa", "aaa", "aaa"], ["abb", "aba", "efg"]]
Sample output:
[0, -1, 1]
I think it can be solved by memorizing the search, but the program needs to run for $$$9^7$$$ (except for the case where all letters are different and the case where there are two identical letters from $$$9^9$$$).
Thank you.
You have the right idea. You are essentially looking for a permutation of the letters which satisfy the conditions. This can be solved with BFS.
When all letters are distinct, the number of distinct states is maximized, or $$$9!$$$. In that case you will start with a valid state so you don't need to search, but suppose you did have to. You can verify whether a state satisfies the condition in linear time. You can expand to neighboring states in linear time by constructing a copy where the elements are swapped. There are at most $$$4 \cdot 9 = 36$$$ transitions to consider from each state, but this can be reduced by avoiding equivalent transitions from the same state. For example, expanding by swapping $$$a$$$ with $$$b$$$ and by swapping $$$b$$$ with $$$a$$$.
If you have all letters distinct except two, then the number of states is $$$\frac{9!}{2!}$$$, since the order of the equivalent elements does not matter. If you have another pair then the number of states is $$$\frac{9!}{2! \cdot 2!}$$$, for the same reasons.
So time and memory complexity will be $$$\mathcal{O}(n! \cdot n)$$$ and in here $$$n=9$$$.