int m, n;
int ans = INT_MAX;
int dx[4] = {0, -1, 0, 1}, dy[4] = {-1, 0, 1, 0};

void dfs(vector<vector<int> >& p, int x, int y, int res) {
    if(res >= ans) return;
    if(x == m - 1 && y == n - 1) {
        ans = min(ans, res);
        return;
    }

    for(int i = 0; i < 4; i ++) {
        int a = x + dx[i], b = y + dy[i];
        if(a >= 0 && a < m && b >= 0 && b < n && p[a][b] != 2) {
            tmp = res;
            if(p[a][b] == 1) res += 1;
            else res += 2;
            dfs(p, a, b, res);
            res = tmp;
        }
    }
}

int minSailCost(vector<vector<int> >& input) {
    // write code here
    m = input.size(), n = input[0].size();
    dfs(input, 0, 0, 0);

    return ans;
}