Problem F
Gap
---- 2003年 会津大会 ----

Let’s play a card game called Gap.
 「ギャップと呼ばれるカードゲーム。」

You have 28 cards labeled with two-digit numbers. The first digit (from 1 to 4) represents the suit of the card, and the second digit (from 1 to 7) represents the value of the card.
 「2桁の数字の付いているカードが28枚ある。左の数字(1から4)はカードのスーツ(ハート、ダイアモンド、クラブ、スペードのこと)を表し、右の数字(1から7)はカードの大きさを表す。」

First, you shuffle the cards and lay them face up on the table in four rows of seven cards, leaving a space of one card at the extreme left of each row. The following shows an example of initial layout.
 「カードを混ぜて、テーブルに7枚ずつ4列をつくり、数字が見えるようにする。4列の左にカード1枚入るスペースを確保しておく。下図参照」

Next, you remove all cards of value 1, and put them in the open space at the left end of the rows: “11” to the top row, “21” to the next, and so on.
 「数字1のカードを左のスペースにもっていき、上から11、21等の順に置く。」

Now you have 28 cards and four spaces, called gaps, in four rows and eight columns. You start moving cards from this layout.
 「これで28枚のカードと4箇所のスペース(ギャップと呼ぶ)が4x8の列になる。ここからゲームがスタート。」

At each move, you choose one of the four gaps and fill it with the successor of the left neighbor of the gap. The successor of a card is the next card in the same suit, when it exists. For instance the successor of “42” is “43”, and “27” has no successor.
 「移動のルールとして、4箇所のギャップのどれかを選び、そのギャップの左隣のカードの次にくるもので埋めないといけない。スーツは同じでないといけない。例えば、"42"のつぎのカードは"43"であり、"27"につぎのカードはない。」

In the above layout, you can move “43” to the gap at the right of “42”, or “36” to the gap at the right of “35”. If you move “43”, a new gap is generated to the right of “16”. You cannot move any card to the right of a card of value 7, nor to the right of a gap.
 「上のレイアウトでは、"43"を"42"の右のギャップにいれることができる。または、"35"の右隣に"36"が移動可能。"43"を移動したら、"16"の右に新しいギャップが空く。しかし、数字7の右にカードを移動することができない。

The goal of the game is, by choosing clever moves, to make four ascending sequences of the same suit, as follows.
 「同じスーツが昇順で並ぶようになればゲームが完成し終了する。」

Your task is to find the minimum number of moves to reach the goal layout.
 「完成するまでの最小移動回数を計算して欲しい。」

Input

The input starts with a line containing the number of initial layouts that follow.
 「入力の1行目に、初期レイアウトの数が入る。」

Each layout consists of five lines --- a blank line and four lines which represent initial layouts of four rows. Each row has seven two-digit numbers which correspond to the cards.
 「個々のレイアウトは5行。1行は空白行、残りの4行はカード4列の最初の並びを表す。」

Output

For each initial layout, produce a line with the minimum number of moves to reach the goal layout. Note that this number should not include the initial four moves of the cards of value 1. If there is no move sequence from the initial layout to the goal layout, produce "-1".
 「個々のレイアウトに対応して、完成までの最短移動回数を表示すること。最初のカードの移動はこの回数に入れないこと。初期レイアウトから完成することは不可能な場合は、-1を表示すること。」

Sample Input

4

12 13 14 15 16 17 21
22 23 24 25 26 27 31
32 33 34 35 36 37 41
42 43 44 45 46 47 11

26 31 13 44 21 24 42
17 45 23 25 41 36 11
46 34 14 12 37 32 47
16 43 27 35 22 33 15

17 12 16 13 15 14 11
27 22 26 23 25 24 21
37 32 36 33 35 34 31
47 42 46 43 45 44 41

27 14 22 35 32 46 33
13 17 36 24 44 21 15
43 16 45 47 23 11 26
25 37 41 34 42 12 31

Output for the Sample Input

0
33
60
-1

Comments are closed.

Post Navigation