Snapcaht 7.19新鲜电面

liuqi627

您需要登录才可以下载或查看附件。没有帐号？注册账号

x

是一道面经题：地里出现过，俗称有墙找路：
题目是一个矩阵里某些

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

晋级了！求加大米啊！！！

何打发123

自己写了一个不知道对不对~各位求指正~

int money = Integer.MAX_VALUE;
public int minCost(int[][] matrix){
if(matrix == null || matrix.length == 0) return -1;
int[][] cost = new int[matrix.length][matrix[0].length];
for(int i = 0; i < cost.length; i++){
Arrays.fill(cost[i], Integer.MAX_VALUE);
}
cost[0][0] = 0;
boolean[][] visited = new boolean[matrix.length][matrix[0].length];
dfs2(matrix, cost, visited, 0, 0, 0);
return money;
}
private void dfs2(int[][] matrix, int[][] cost, boolean[][] visited, int x, int y, int cur){
if(x < 0 ||x >= matrix.length || y < 0 || y >= matrix[0].length || visited[x][y] == true) return;
if(cur > cost[x][y]) return;
visited[x][y] = true;
if(matrix[x][y] == 9){
//System.out.println(money);
//money = Math.min(cur, money);
money = cur;
//return;
}
if(matrix[x][y] == 5){
//cost[x][y] = Math.min(cost[x][y], cur + 1);
cost[x][y] = cur + 1;
}else{
//cost[x][y] = Math.min(cost[x][y], cur);
cost[x][y] = cur;
}
// System.out.println(x + " " + y + " " + cost[x][y]);
int[] surroundx = new int[]{-1, 1, 0, 0};
int[] surroundy = new int[]{0, 0, -1, 1};
for(int i = 0; i < 4; i++){
dfs2(matrix, cost, visited, x + surroundx[i], y + surroundy[i], cost[x][y]);
}
visited[x][y] = false;
}
public static void main(String[] args) {
Solution s = new Solution();
int[][] m = {
{1, 0, 5, 5, 5, 0},
{5, 0, 0, 5, 5, 0},
{5, 5, 0, 0, 0, 0},
{5, 5, 0, 0, 5, 0},
{9, 5, 5, 0, 0, 0}
};
System.out.println(money);
}
}

复制代码

何打发123

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

liurudahai

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

StellaJiang

楼主是找人内推的吗，还是自己投的？

wtcupup

用BFS 然后Follow up用DP ?

liuqi627

StellaJiang 发表于 2016-7-21 16:37
楼主是找人内推的吗，还是自己投的？

推的，推的，推的，推的，推的，推的

谎言之躯

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

谎言之躯

follow up是要求把整条路线输出吗？

何打发123

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

谎言之躯

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

pupuchan1116

liuqi627 发表于 2016-7-21 16:56
推的，推的，推的，推的，推的，推的

楼主如果能推的话可否留一个您的邮箱我想把简历发给您谢谢～