新砖混

Question

你有n块砖排列在桌子上。每个人都有一封信。你的任务是重新排列这些砖块，使它们上的字母创建一些指定的铭文。在重新排列的时候，你只能用指定的字母交换相邻的砖块（你给出了m对（a1，b1），...，（am，bm），而且你只允许在其中一个砖块上用ai交换砖块，第二，对于某些i = 1，..，m）。您应该检查是否有可能实现这一点 - 如果是 - 计算所需交换次数最少。

输入

上有输入的第一行一个整数℃。然后是c个测试用例：它们中的每一个都由长度不超过100000的两行小写字母（a..z）（开始和结束配置的描述）组成，在下一行中有一个整数m，然后m行有两个字母ai，bi中的每一个。

输出

对于每个测试情况下，你应该打印-1，如果这是不可能重新排列砖或互换的最小数目，如果它是可能的（如果是这样，输出该值模232）。

Input: 
    4 
    ab 
ba 
0 
abc 
cba 
3 
ab 
cb 
ca 
cabbbc 
cbabbc 
1 
ab 
abba 
baab 
1 
ab 

Output: 
-1 
3 
1 
2 

我没有明白的问题可以在任何一个可以帮助我了解的测试用例没有必要指导我在给予提示和算法只是解释我的问题，感谢名单

Answer 1

您有4个测试用例。

Case 1: 
start config: `ab` 
end config: `ba` 
allowed adjacent swaps: none 
result: -1 - without any allowed swap, you can't get from `ab` to `ba` 

Case 2: 
start config: `abc` 
end config: `cba` 
allowed adjacent swaps: `(ab)`,`(cb)`,`(ca)` 
result: 3 
example solution: `abc -> (cb)@(1,2) -> acb -> (ca)@(0,1) -> cab -> (ab)@(1,2) -> cba` 

Case 3: 
start config: `cabbbc` 
end config: `cbabbc` 
allowed adjacent swaps: `(ab)` 
result: 3 
example solution: `cabbbc -> (ab)@(1,2) -> cabbbc` 


Case 4: 
start config: `abba` 
end config: `baab` 
allowed adjacent swaps: `(ab)` 
result: 2 
example solution: `abba -> (ab)@(2,3) -> abab -> (ab)@(0,1) -> baab` 

Answer 2

4 - 4 testcases 
(now two lines which were said, they define strings to swap one into another) 
ab 
ba 
0 - zero strings which define bricks 

Now, you can't rearrange nothing, because you have no strigns. return -1. 

Now the secons testcase: 
(two lines which define strings to trasform one into another) 
abc 
cba 
3 - three bricks 
ab 
cb 
ca 
And above we ahve three bricks. So we can, to my understanding, swap these bricks letters, so swap a with b, c with b, and c with a, so basically all possible swaps are allowed). 

Third testcase - analogical to the second, but you're only allowed to swap "a" with "b". 
cabbbc 
cbabbc 
1 
ab 

And so on... 

abba 
baab 
1 
ab 

这是我的理解任务。

Answer 3

测试用例是一个开始和结束位置（两行字符）后跟一个数字。该数字描述了有多少可能的转换。然后有可能的过渡。因此，在你的例子中，第一个测试案例是“当没有你可以交换的信件时，从ab到ba需要多少步？” （答案-1是“不可能”的答案。）第二个测试案例是“如果可以交换ab，cb或ca，从abc到cba需要多少步？”答案是3.第三个测试案例是“如果可以交换ab，从cabbbc到cbabbc需要多少步？”等

Answer 4

让我解释一下测试用例（以重新排列的顺序）

ab 
ba 
0 

你不能从“AB”到“八”，因为没有互换允许=>输出-1

cabbbc 
cbabbc 
1 
ab 

您可以切换邻近a和b，好的，只需在第二个和第三个字符上进行一次即可。 =>输出1

abba 
baab 
1 
ab 

同样在这里，前两个，最后两个，提出了两个互换=>输出2

abc 
cba 
3 
ab 
cb 
ca 

不能互换a和c直接，因为他们不相邻。相反，将a与b交换并获得bac。然后，与c交换a并获得bca。在最后，交换b与c，并得到cba =>输出3

如果可以交换“AB”到“八”，你也可以换用“巴”到“AB”。这在任务描述中并不明显，但示例测试用例说明了这一点。