首页 > 8.21网易开发笔试第四题
头像
杂毛小鸡
发布于 2021-08-21 18:38
+ 关注

8.21网易开发笔试第四题

第四题我是用的dfs + 剪枝写的 只过了66%
有大佬帮忙看看哪还有问题吗

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;
}

 

全部评论

(2) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐