import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * <p>
     * 计算最小航行费用
     *
     * @param input int整型二维数组 二维网格
     * @return int整型
     */
    int minRes = Integer.MAX_VALUE;
    int xx[] = {1, 0, -1, 0};
    int yy[] = {0, -1, 0, 1};
    int endX = 0, endY = 0;
    boolean[][] vis;

    public int minSailCost(int[][] input) {
        endX = input.length - 1;
        endY = input[0].length - 1; // write code here
        vis = new boolean[input.length][input[0].length];

        dfs(0, 0, 0, input);
        vis[0][0] = true;
        if (minRes == Integer.MAX_VALUE)
            return -1;
        else
            return minRes;
    }

    public void dfs(int x, int y, int ans, int[][] a) {
        if (ans > minRes)       // 已经有更小的了 ，剪枝直接返回
            return;
        System.out.println(x + " " + y + " " + ans);
        if (x == endX && y == endY) {       //到达重点
            minRes = Math.min(minRes, ans);
            System.out.println("------------------");
            return;

        }
        for (int i = 0; i < 4; i++) {
            int dx = x + xx[i];
            int dy = y + yy[i];

            if (dx >= 0 && dx <= endX && dy >= 0 && dy <= endY) {
                if (!vis[dx][dy] && a[dx][dy] != 2) {  //访问过或者是障碍物
                    vis[dx][dy] = true;
                    int cost = 1;
                    if (a[dx][dy] == 0)
                        cost = 2;
                    else if (a[dx][dy] == 1)
                        cost = 1;
                    dfs(dx, dy, ans + cost, a);
                    vis[dx][dy] = false;
                }
            }
        }
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[][] a = new int[][]{{1, 1, 1, 1, 0}, {0, 1, 0, 1, 0}, {1, 1, 2, 1, 1}, {0, 2, 0, 0, 1}};
        //int[][] a = new int[][]{{1, 1, 1, 1, 1}, {2, 2, 2, 2, 1}, {1, 1, 1, 1, 1}, {1, 2, 2, 2, 2}, {1, 2, 1, 1, 1}};
        System.out.println(sol.minSailCost(a));
    }
}