a281. TOI 2024/06 潛力組：移動盤面

題目描述

有一塊 M 列、N 欄的棋盤，放著編號 1 到 K 的 K 個矩形物件。物件彼此不重疊，空格以 0 表示，其餘格子上的數字就是占用該格的物件編號。

給定初始盤面與目標盤面。每一步可以選一個完整物件，向上、下、左或右平移一格；移動後必須仍在棋盤內，且不能與其他物件重疊。物件不能旋轉。

請計算從初始盤面變成目標盤面最少需要幾步。

輸入格式

第一行包含三個正整數 M、N、K。接下來 M 行描述初始盤面，再接下來 M 行描述目標盤面；每行包含 N 個以空白分隔的非負整數。

• 1 ≤ M、N ≤ 5，且 M × N ≤ 20
• 1 ≤ K ≤ 5
• 盤面中的數字介於 0 與 K；每個編號在兩個盤面中都恰好構成一個相同長寬的矩形。

輸出格式

輸出最少移動步數；若無法到達目標盤面，輸出 -1。

來源

TOI 2024 年 6 月潛力組〈移動盤面〉。本敘述重新撰寫；範例與測資為另行設計。 https://tpmso.k12ea.gov.tw/toi/wp-content/uploads/question/202406/Puzzle.pdf