public class password_table2 {
    public static void main(String[] args) {
        String[] s = new String[]{"abc", "efg","hij"};
        String ss = "bfgcij";
        int a = step(s, ss);
        //System.out.println("step:" + step);
    }
    static int[][] sides = {{1,1}, {1, 0}, {-1, 0}, {-1, -1}, {0, 1}, {0, -1}, {1, -1}, {-1, 1}};
    public static int step(String[] password, String s){
        char[][] passwordchar = new char[3][3];
        for(int i = 0; i < 3; i++){
            passwordchar[i] = password[i].toCharArray();
        }

        char[] wordchar = s.toCharArray();
        int len = wordchar.length;
        Map<Character, int[]> map = new HashMap<>();
        for(int i = 0; i < passwordchar.length; i++){
            for(int j = 0; j < passwordchar[0].length; j++){
                char cc = passwordchar[i][j];

                int[] tempin = new int[]{i, j};
                map.put(cc, tempin);
            }
        }


        int[] start = map.get(wordchar[0]);
        int startx = start[0];
        int starty = start[1];

        Deque<int[]> queue = new LinkedList<>();
        queue.add(new int[]{startx, starty});
        int index = 0;
        int step = 0;

        while(!queue.isEmpty()){
            int size = queue.size();

            for(int i = 0; i < size; i++){
                int[] temp = queue.poll();
                int tempx = temp[0];
                int tempy = temp[1];
//                if(passwordchar[tempx][tempy] == wordchar[index]){
//                    index++;
//                }
                if(passwordchar[tempx][tempy] == wordchar[index]){
                    step++;
                    index++;
                }
                for(int j = 0; j < sides.length; j++){
                    int x1 = tempx + sides[j][0];
                    int y1 = tempy + sides[j][1];
//                    if(index < len && passwordchar[x1][y1] == wordchar[index]){
//                        index++;
//                    }
                    if(x1 >= 0 && x1 < 3 && y1 >= 0 && y1 < 3){
                        queue.add(new int[]{x1, y1});
                    }

                }
            }
            //step++;
        }
        return step - 1;
    }

}