阿里编程第一道题
阿里第一题，求最小路径，用dfs做的，最后没来得及提交验证，不知道能不能AC，本地测试没问题。
package alibaba;
import java.util.HashSet;
import java.util.Scanner;
public class Problem1 {
private static HashSet<Integer> list = new HashSet<Integer>();
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String line = scanner.nextLine();
int n = Integer.parseInt(line); //第一个数字n
int[][] area = new int[n][n];
for (int i = 0; i < n; i++) {
line = scanner.nextLine();
String[] split = line.split(",");
if (split.length != n) {
throw new IllegalArgumentException("错误输入");
}
int j = 0;
for (String num : split) {
area[i][j++] = Integer.parseInt(num);
}
}
int minimumTimeCost = getMinimumTimeCost(n, area);
System.out.println(minimumTimeCost);
}
/** 请完成下面这个函数，实现题目要求的功能 **/
/** 当然，你也可以不按照这个模板来作答，完全按照自己的想法来 ^-^ **/
private static int getMinimumTimeCost(int n, int[][] area) {
int cols = area[0].length;
int price = 0;
int min = Integer.MAX_VALUE;
for(int col=0; col<cols; col++) {
if(col==5) System.out.println("hehe");
dfs(area, 0, col, price);
}
for(Integer data:list) {
if(data<min) {
min = data;
}
}
return min;
}
private static void dfs( int[][] area, int row, int col, int price) {
if(col>=area[0].length) return;
if(row>=area.length) {list.add(price); return;}
int choose1=0, choose2=0;
choose1 = area[row+1][col];//向下的代价
if(col+1>=area[0].length) {
choose2 = 100000;//向右的代价
} else {
choose2 = area[row][col+1];//向右的代价
}
int price1 = price + choose1;
int price2 = price + choose2;
dfs(area, row+2, col, price1);
dfs(area, row, col+2, price2);
}
}
/**
6
1,2,3,4,5,6
2,2,3,4,4,3
2,4,1,2,1,3
3,2,1,1,2,4
3,2,1,1,1,2
2,4,2,4,5,1
**/
#阿里巴巴##笔试题目#