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