Help me with this problem, I’m TLE.

Revision en2, by _Redstone_c_, 2023-08-23 15:22:14

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.

Tags problem, grid

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English _Redstone_c_ 2023-08-23 15:22:14 4
en1 English _Redstone_c_ 2023-08-23 15:21:22 835 Initial revision (published)