高级农民
- 积分
- 2288
- 大米
- 颗
- 鳄梨
- 个
- 水井
- 尺
- 蓝莓
- 颗
- 萝卜
- 根
- 小米
- 粒
- 学分
- 个
- 注册时间
- 2015-8-24
- 最后登录
- 1970-1-1
|
试着写了一下第二题、假设左上角是入口右下角是出口。matrix里的数字都大于等于0。- public class ShortestPath {
- int shortest = Integer.MAX_VALUE;
- String resPath = "";
- public String solution(int[][] matrix) {
- helper(matrix, "", 0, 0, 0);
- return resPath;
- }
- private void helper(int[][] matrix, String path, int curMax, int i, int j) {
- if (i < 0 || i >= matrix.length || j < 0 || j >= matrix[0].length) return;
- if (i == matrix.length - 1 && j == matrix[0].length - 1) {
- if (path.length() + 1 < shortest) {
- shortest = path.length() + 1;
- resPath = path + matrix[i][j];
- }
- return;
- }
- if (matrix[i][j] == -1 || matrix[i][j] < curMax) return;
- int originalVal = matrix[i][j];
- matrix[i][j] = -1;
- helper(matrix, path + originalVal, originalVal, i + 1, j);
- helper(matrix, path + originalVal, originalVal, i - 1, j);
- helper(matrix, path + originalVal, originalVal, i, j + 1);
- helper(matrix, path + originalVal, originalVal, i, j - 1);
- matrix[i][j] = originalVal;
- }
- public static void main(String[] args) {
- ShortestPath solution = new ShortestPath();
- int[][] matrix = new int[][]{{1, 2, 3}, {1, 1, 1}, {2, 3, 4}};
- System.out.println(solution.solution(matrix));
- }
- }
复制代码
|
|