a074. 最短拼字路

題目描述

未來的鍵盤不靠按鍵，而是讓一個小游標在字母方格上移動。鍵盤中每格寫著一個大寫字母，# 則是游標無法穿越的障礙。你要讓游標依照順序輸入指定的目標字串，同時盡可能少移動。

一開始可以免費選擇任意一格寫著目標字串第一個字母的位置，並立即輸入這個首字。之後每次移動只可往上、下、左、右的一個相鄰格走一步，不能跨牆或走出鍵盤。抵達新格子時，若上面的字母恰好等於下一個尚未輸入的字母，就會自動輸入它；否則只是經過，先不輸入任何字。一次移動最多輸入一個字母。

可以多次走進同一格，也可以為了繞過障礙走過暫時用不到的字母；但已經輸入的字母不能取消或改順序。計算步數時，只計起點之後的移動：如果目標只有一個字，找到起點就能用 0 步完成。請求出能完整輸入目標字串的最少步數；若沒有任何可行走法，就輸出 -1。

輸入格式

第一行 R C，接著 R 行鍵盤；最後一行是目標字串 s。

限制

• 1 ≤ R, C ≤ 20；1 ≤ s 長度 ≤ 30
• 鍵盤只含大寫字母與 #；s 只含大寫字母

輸出格式

輸出最少移動步數；若無法完成則輸出 -1。

範例1

範例輸入：

2 3
ABC
D#E
ACE

範例輸出：

3

從 A 出發，經 B 路過，到 C 再到 E，共走 3 步。

範例2

範例輸入：

1 3
A#B
AB

範例輸出：

-1

雖然鍵盤上有 A 和 B，但兩格被牆隔開，游標不能從 A 走到 B。