h708: 神秘的箱子
Tags : 群論 規律
Accepted rate : 1人/3人 ( 33% ) [非即時]
評分方式:
Special

最近更新 : 2022-04-04 16:15

Content

阿祁找到一個鎖起來的箱子,他想要把它打開,但是上面的鎖很複雜。

下圖是鎖的長相:

0 1 3 2 4

1 4 2 0 3

這個鎖的大小是 2 x N 的方格(長得像上方那樣,上方以N=5舉例),他首先把它看成上下兩部分,變成兩個 1 x N 的長條形,發現上面和下面兩個部分的格子裡都有1N - 1各一個,以及一個空格(空格以0表示)。另外阿祁發現了上面寫著要把鎖變成下列的樣子才能解鎖:

0 1 2 3 4

0 1 2 3 4

解鎖的方式是阿祁每一步可以隨意選擇一個有數字的格子,並且把它移動到上下左右鄰近的空格。

可是他不知道怎麼運用移動的方法解鎖,所以請您幫幫他吧!幫忙他寫一個程式,算出要甚麼順序移動才可復原,您可以印出任何解法,只要不超過40000步且正確都可以通過。

保證對於所有測試資料滿足:

2 ≤ N ≤ 50
陣列的兩行都各有12、…、N-1一個(不一定照順序),以及一個0代表空格。

Input

第一行有一整數N代表原陣列長度為N,有1~N-1的數字。
接下來兩行,代表阿祁拿到的鎖,兩行都會有0~N-1數字各一個,其中0代表那一排本來的空格。

Output

第一行輸出K代表步數,注意須滿足K≤40000,如果沒有符合的解只需輸出-1
接著輸出K行,每行輸出四個數字,前面兩個代表要移動的數字本來的座標,後面兩個代表要移動到的座標,對於座標表示:請先輸出長度為2的那個維度,接著輸出長度為N的那邊,注意本題為1-indexed,座標如1 3 1 2代表從(1,3)移動到(1,2)

Sample Input #1
3
1 0 2
2 1 0
Sample Output #1
5
2 2 1 2
2 1 2 2
1 1 2 1
2 2 2 3
2 1 2 2
Sample Input #2
2
0 1
0 1
Sample Output #2
0
測資資訊:
記憶體限制: 256 MB
公開 測資點#0 (10%): 1.0s , <1K
公開 測資點#1 (10%): 1.0s , <1K
公開 測資點#2 (10%): 1.0s , <1K
公開 測資點#3 (10%): 1.0s , <1K
公開 測資點#4 (10%): 1.0s , <1K
公開 測資點#5 (10%): 1.0s , <1K
公開 測資點#6 (10%): 1.0s , <1K
公開 測資點#7 (10%): 1.0s , <1K
公開 測資點#8 (10%): 1.0s , <1K
公開 測資點#9 (10%): 1.0s , <1K
Hint :

上方輸出的流程如下方:
1 0 2
2 1 0

1 1 2
2 0 0

1 1 2
0 2 0

0 1 2
1 2 0

0 1 2
1 0 2

0 1 2
0 1 2

Tags:
群論 規律
出處:
Chi's Coding Problem [管理者:
linlincaleb@... (臨末之頌)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」