Problem:


On-Screen Keyboard

  

    You are to input a string with an OSK (on-screen keyboard).
    A remote control with five buttons, four arrows and an OK (Fig. B-1),
    is used for the OSK.
    Find the minimum number of button presses required
    to input a given string with the given OSK.

  
    
    
      
      Fig. B-1 Remote control 
      
    
  

  
    
    
      
      Fig. B-2 An on-screen keyboard 
      
    
  

  
    
    

      
	
Character to inputMove of highlighted cellsButton presses

      
      
	
I&rarr;,&rarr;,&rarr;,&rarr;,&rarr;,&rarr;,&rarr;,&rarr;,OK (9 presses)

	
C&larr;,&larr;,&larr;,&larr;,&larr;,&larr;,OK (7 presses)

	
P&darr;,&rarr;,&rarr;,&rarr;,&rarr;,OK (6 presses)

	
C&uarr;,&larr;,&larr;,&larr;,&larr;,OK (6 presses)

      
    

    
    
      
      Fig. B-3 The minimum steps to input &ldquo;ICPC&rdquo; with the OSK in Fig. B-2
      
    
  

  

    The OSK has cells arranged in a grid, each of which has a
    character in it or is empty.
    No two of the cells have the same character.
  

  

    One of the cells of the OSK is highlighted, and
    pressing the OK button will input the character in that cell,
    if the cell is not empty.
  

  

    Initially, the cell at the top-left corner is highlighted.
    Pressing one of the arrow buttons will change the highlighted cell
    to one of the adjacent cells in the direction of the arrow.
    When the highlighted cell is on an edge of the OSK,
    pushing the arrow button with the direction to go out of the edge
    will have no effect.
  

  

    For example, using the OSK with its arrangement shown in Fig. B-2,
    a string &ldquo;ICPC&rdquo; can be input with 28 button presses
    as shown in Fig. B-3, which is the minimum number of presses.

  

  

    Characters in cells of the OSKs are any of a lowercase letter
    (&lsquo;a&rsquo;, &lsquo;b&rsquo;, ..., &lsquo;z&rsquo;),
    an uppercase letter
    (&lsquo;A&rsquo;, &lsquo;B&rsquo;, ..., &lsquo;Z&rsquo;),
    a digit
    (&lsquo;0&rsquo;, &lsquo;1&rsquo;, ..., &lsquo;9&rsquo;),
    a comma (&lsquo;,&rsquo;),
    a hyphen (&lsquo;-&rsquo;),
    a dot (&lsquo;.&rsquo;),
    a slash (&lsquo;/&rsquo;),
    a colon (&lsquo;:&rsquo;),
    a semicolon (&lsquo;;&rsquo;),
    or an at sign (&lsquo;@&rsquo;).

  

  

Input

The input consists of at most 100 datasets, each in the following format.

  
    

      h w

      r1

      ...

      rh

      s
    

  

The two integers h and w in the first line are
the height and the width of the OSK, respectively.
They are separated by a space, and satisfy 1 ≤ h ≤ 50 and 1 ≤ w ≤ 50. 

  Each of the next h lines gives a row of the OSK.
The i-th row, ri is a string of length w.
  The characters in the string corresponds to the characters
in the cells of the i-th row of the OSK
or an underscore (&lsquo;_&rsquo;) indicating an empty cell,
  from left to right.

  The given OSK satisfies the conditions stated above.

  The next line is a string s to be input. Its length is between 1 and 1000, inclusive.
  All the characters in s appear in the given OSK.
  Note that s does not contain underscores.

The end of the input is indicated by a line containing two zeros.

Output

  For each dataset, output a single line containing an integer indicating the minimum number of button presses required to input the given string with the given OSK.

Sample Input

3 9
ABCDEFGHI
JKLMNOPQR
STUVWXYZ_
ICPC
5 11
___________
____A______
________M__
___________
_C_________
ACM
4 21
1_2_3_4_5_6_7_8_9_0_-
QqWwEeRrTtYyUuIiOoPp@
AaSsDdFfGgHhJjKkLl;_:
ZzXxCcVvBbNnMm,_._/__
ICPC2019,AsiaYokohamaRegional,QualificationRound
0 0

Output for the Sample Input

28
23
493



Sample input:
3 9
ABCDEFGHI
JKLMNOPQR
STUVWXYZ_
ICPC
5 11
___________
____A______
________M__
___________
_C_________
ACM
4 21
1_2_3_4_5_6_7_8_9_0_-
QqWwEeRrTtYyUuIiOoPp@
AaSsDdFfGgHhJjKkLl;_:
ZzXxCcVvBbNnMm,_._/__
ICPC2019,AsiaYokohamaRegional,QualificationRound
0 0


Sample output:
28
23
493

Submission status: Accepted

Solution code:
while True:
    h, w = map(int, input().split())
    if h == w == 0:
        break
    mp = {}
    for r in range(h):
        s = input()
        for c in range(w):
            mp[s[c]] = [r, c]
    s = input()
    now = [0, 0]
    ans = 0
    for i in range(len(s)):
        to = mp[s[i]]
        ans += abs(now[0] - to[0]) + abs(now[1] - to[1]) + 1
        now = to
    print(ans)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
while True:
	rr=[]
	h,w=map(int,input().split())
	if h==w==0:
		break
	else:
		for i in range(h):
			r=input().rstrip()
			rr.append(r)
		s=input().rstrip()
		ans=0
		now=[0,0]
		for i in range(len(s)):
			for j in range(h):
				for k in range(w):
					if rr[j][k]==s[i]:
						ans+=abs(now[0]-j)+abs(now[1]-k)
						now=[j,k]
		print(ans+len(s))

Submission status: Accepted

Solution code:
while 1:
    h, w = map(int, input().split())
    if h == 0:
        break
    d = {}
    for i in range(h):
        s = input()
        for j in range(w):
            if s[j] != '_':
                d[s[j]] = [j, i]
    s = input()
    cnt = 0
    for i in range(len(s)):
        if i == 0:
            cnt += d[s[i]][0] + d[s[i]][1] + 1
        else:
            cnt += abs(d[s[i]][0]-d[s[i-1]][0]) + abs(d[s[i]][1]-d[s[i-1]][1]) + 1
    print(cnt)

Submission status: Accepted

Solution code:
#!/usr/bin/python3

import array
from fractions import Fraction
import functools
import itertools
import math
import os
import sys


def main():
    while True:
        H, W = read_ints()
        if (H, W) == (0, 0):
            break
        R = [inp() for _ in range(H)]
        S = inp()
        print(solve(H, W, R, S))


def solve(H, W, R, S):
    pos_map = {}
    for y in range(H):
        for x in range(W):
            c = R[y][x]
            if c != '_':
                pos_map[c] = (x, y)

    ans = 0
    cx = 0
    cy = 0
    for c in S:
        x, y = pos_map[c]
        ans += abs(x - cx) + abs(y - cy) + 1
        cx, cy = x, y

    return ans


###############################################################################
# AUXILIARY FUNCTIONS

DEBUG = 'DEBUG' in os.environ


def inp():
    return sys.stdin.readline().rstrip()


def read_int():
    return int(inp())


def read_ints():
    return [int(e) for e in inp().split()]


def dprint(*value, sep=' ', end='\n'):
    if DEBUG:
        print(*value, sep=sep, end=end)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
スクリーンキーボード
https://onlinejudge.u-aizu.ac.jp/challenges/sources/ICPC/Prelim/1633

"""
import sys


def solve(h, w):
    keyboard = dict()
    for y in range(h):
        for x, ch in enumerate(input()):
            keyboard[ch] = (x, y)

    cx, cy = 0, 0
    ans = 0
    for ch in input():
        nx, ny = keyboard[ch]
        ans += (abs(nx - cx) + abs(ny - cy) + 1)
        cx, cy = nx, ny
    return ans


def main(args):
    while True:
        h, w = map(int, input().split())
        if h == 0 and w == 0:
            break
        ans = solve(h, w)
        print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
import os,re,sys,operator
from collections import Counter,deque
from operator import itemgetter
from itertools import accumulate,combinations,groupby
from sys import stdin,setrecursionlimit
from copy import deepcopy
import heapq

setrecursionlimit(10**6)
while 1:
    h,w=map(int,stdin.readline().rstrip().split())
    if (h,w)==(0,0):
        break
    a=[stdin.readline().rstrip() for _ in range(h)]
    s=input()
    nx,ny=0,0
    o=0
    cnt=0
    for i in s:
        nh=0
        for j in range(h):
            if i in a[j]:
                o=a[j].index(i)
                cnt+=(abs(nx-o)+abs(ny-nh)+1)
                break
            else:
                nh+=1
        nx,ny=o,nh
    print(cnt)

Submission status: Accepted

Solution code:
while True:
    h,w = map(int,input().split())
    if(h+w == 0):
        break
    li = list()
    for i in range(h):
        s = input()
        li.append(s)
    d = dict()
    for i,l in enumerate(li):
        for j,char in enumerate(l):
            d[char] = (i,j)
    target = input()
    ans = 0
    now = (0,0)
    for t in target:
        next = d[t]
        ans += abs(now[0]-next[0]) + abs(now[1]-next[1])
        now=next
    print(ans + len(target))

Submission status: Accepted

Solution code:
# coding=utf-8

###
### for python program
###

import sys
import math

# math class
class mymath:
    ### pi
    pi = 3.14159265358979323846264338

    ### Prime Number
    def pnum_eratosthenes(self, n):
        ptable = [0 for i in range(n+1)]
        plist = []

        for i in range(2, n+1):
            if ptable[i]==0:
                plist.append(i)
                for j in range(i+i, n+1, i):
                    ptable[j] = 1
        return plist

    def pnum_check(self, n):
        if (n==1):
            return False
        elif (n==2):
            return True
        else:
            for x in range(2,n):
                if(n % x==0):
                    return False
            return True

    ### GCD
    def gcd(self, a, b):
        if b == 0:
            return a
        return self.gcd(b, a%b)

    ### LCM
    def lcm(self, a, b):
        return (a*b)//self.gcd(a,b)

    ### Mat Multiplication
    def mul(self, A, B):
        ans = []
        for a in A:
            c = 0
            for j, row in enumerate(a):
                c += row*B[j]
            ans.append(c)
        return ans
    
    ### intチェック
    def is_integer(self, n):
        try:
            float(n)
        except ValueError:
            return False
        else:
            return float(n).is_integer()

    ### 幾何学問題用
    def dist(self, A, B):
        d = 0
        for i in range(len(A)):
            d += (A[i]-B[i])**2            
        d = d**(1/2)
        return d

    ### 絶対値
    def abs(self, n):
        if n >= 0:
            return n
        else:
            return -n

mymath = mymath()

### output class
class output:
    ### list
    def list(self, l):
        l = list(l)
        #print(" ", end="")
        for i, num in enumerate(l):
            print(num, end="")
            if i != len(l)-1:
                print(" ", end="")
        print()

output = output()

### input sample
#i = input()
#N = int(input())
#A, B, C = [x for x in input().split()]
#N, K = [int(x) for x in input().split()]
#inlist = [int(w) for w in input().split()]

#R = float(input())
#A.append(list(map(int,input().split())))

#for line in sys.stdin.readlines():
#    x, y = [int(temp) for temp in line.split()]

#abc list
#abc = [chr(ord('a') + i) for i in range(26)]

### output sample
# print("{0} {1} {2:.5f}".format(A//B, A%B, A/B))
# print("{0:.6f} {1:.6f}".format(R*R*math.pi,R*2*math.pi))
# print(" {}".format(i), end="")

def printA(A):
    N = len(A)
    for i, n in enumerate(A):
        print(n, end='')
        if i != N-1:
            print(' ', end='')
    print()

# リスト内包表記 ifあり
# [x-k if x != 0 else x for x in C]

# ソート
# N = N.sort()

# 10000個の素数リスト
# P = mymath.pnum_eratosthenes(105000)

def get_input():
    N = []
    while True:
        try:
            N.append(input())
            #N.append(int(input()))
            #N.append(float(input()))
        except EOFError:
            break
    return N

while True:
    H, W = [int(x) for x in input().split()]
    if H==0 and W==0:
        break
    R = []
    for i in range(H):
        R.append(input())
    S = input()

    count = 0
    x = 0
    y = 0
    for s in S:
        for i, row in enumerate(R):
            for j, r in enumerate(row):
                if s == r:
                    count += (mymath.abs(i-x)+mymath.abs(j-y)+1)
                    x = i
                    y = j
                    break

    print(count)

Submission status: Accepted

Solution code:
while 1:
    H, W = map(int, input().split())
    if H == 0:
        break
    P = {}
    for i in range(H):
        r = input()
        for j, c in enumerate(r):
            P[c] = (i, j)
    S = input()
    ans = len(S)
    px = 0; py = 0
    for c in S:
        x, y = P[c]
        ans += abs(x - px) + abs(y - py)
        px = x; py = y
    print(ans)