0

テーブルの上にn個のレンガが一列に並んでいます。それらのそれぞれにちょうど1つの文字があります。あなたの仕事は、それらのレンガを再配置して、それらの文字が特定の碑文を作成するようにすることです。再配置中は、指定された文字で隣接するブリックのみを交換できます（mペア（a1、b1）、...、（am、bm）が与えられ、そのうちの1つでai、第二に、いくつかのi = 1、..、m）。これを達成できるかどうかを確認する必要があります。可能である場合は、必要最小限のスワップ数を計算します。

入力

入力の最初の行に単一の整数cがあります。次に、c個のテストケースが続きます。それぞれは、長さが100000を超えない2行の小文字（a..z）（開始構成と終了構成の説明）、次の行に1つの整数m、次に2文字の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

私は質問を理解していません誰かがテストケースを理解するのを助けることができますヒントやアルゴリズムを与えることで私を導く必要はありません質問を説明するだけです、ありがとう

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 
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

テストケースは、開始位置と終了位置（2行の文字）の後に数字が続きます。数字は、可能な遷移がいくつあるかを示しています。次に、可能な遷移があります。したがって、あなたの例では、最初のテストケースは、「交換できる文字がない場合、abからbaに移動するのに何ステップかかりますか？」です。（答え-1は「不可能」の答えです。）2番目のテストケースは、「ab、cb、またはcaを交換できる場合、abcからcbaに移動するのに何ステップかかりますか？」です。答えは3です。3番目のテストケースは、「abを交換できる場合、cabbbcからcbabbcに移動するのに何ステップかかりますか？」です。等

于 2013-02-24T21:51:29.073 に答える
0

テストケースを（並べ替えて）説明させてください

ab
ba
0

スワップが許可されていないため、「ab」から「ba」に移動することはできません=>出力-1

cabbbc
cbabbc
1
ab

隣接aして交換することができますb、まあ、2番目と3番目の文字で1回だけそれを行います。=>出力1

abba
baab
1
ab

ここでも同じですが、最初の2つと最後の2つは、2つのスワップを行います=>出力2

abc
cba
3
ab
cb
ca

a隣接していないため、c直接スワップすることはできません。代わりに、と交換aしbて取得しますbac。次に、と交換aしcて取得しますbca。最後に、と交換bして=>出力cを取得しますcba3

「ab」を「ba」に交換できる場合は、「ba」を「ab」に交換することもできます。これはタスクの説明からは明らかではありませんでしたが、サンプルテストケースはこれを明確にしています。

于 2013-02-24T21:54:21.630 に答える