0

你有 n 块砖在桌子上排成一行。他们每个人上都只有一个字母。你的任务是重新排列这些砖块,以便它们上面的字母创建一些指定的铭文。在重新排列时,您只能交换具有指定字母的相邻砖块(给定 m 对 (a1,b1),...,(am,bm) 并且您只能在其中一个上交换带有 ai 和 bi 的砖块第二,对于某些 i=1,..,m)。您应该检查是否有可能实现这一点 - 如果是的话 - 计算最少需要的交换次数。

输入

输入的第一行有一个整数 c。然后是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

我不明白这个问题任何人都可以帮助我理解测试用例不需要指导我给出提示和算法只是解释我这个问题,thanx

4

4 回答 4

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`
于 2013-02-24T21:58:24.710 回答
0

让我解释一下测试用例(按重新排列的顺序)

ab
ba
0

您不能从“ab”到“ba”,因为不允许交换 => 输出-1

cabbbc
cbabbc
1
ab

您可以交换相邻ab,并且,只需在第二个和第三个字符上执行一次。=> 输出1

abba
baab
1
ab

同样在这里,前两个和后两个,进行两次交换 => 输出2

abc
cba
3
ab
cb
ca

您不能直接交换ac因为它们不相邻。相反,交换ab获取bac. 然后,交换ac获取bca. 最后,交换bc获取cba=> 输出3

如果你可以把“ab”换成“ba”,你也可以把“ba”换成“ab”。这在任务描述中并不明显,但示例测试用例清楚地说明了这一点。

于 2013-02-24T21:54:21.630 回答
0
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

这就是我对任务的理解。

于 2013-02-24T21:49:15.080 回答
0

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

于 2013-02-24T21:51:29.073 回答